[数据结构与算法]树链剖分（轻重链） 学习总结

前导知识：

重儿子：对于每一个非叶子节点，它的儿子中 儿子数量最多的那一个儿子 为该节点的重儿子
轻儿子：对于每一个非叶子节点，它的儿子中 非重儿子 的剩下所有儿子即为轻儿子
叶子节点没有重儿子也没有轻儿子
重边：连接任意两个重儿子的边叫做重边
轻边：剩下的即为轻边
重链：相邻重边连起来的 连接一条重儿子 的链叫重链
对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链
每一条重链以轻儿子为起点

效果：

通过两边DFS，处理出来每个节点的各种信息，同时根据第二遍DFS优先DFS重链的DFS序得到每个节点的新节点编号，新节点编号可以使得重链上的点，子树上的点是连续的，和线段树搭配，便于操作。

两种情况：

①如果是点权，直接读入即可。
②如果是边权，因为 边数 = 点数 - 1，DFS预处理一下，一个点的点权代表这个点到这个点的父亲节点的权重，注意此时如果求x到y的边权和，要减去LCA（x，y）的点权，因为这条边不在x—>y的路径上。

代码加详解

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize (Ofast)
#define fastio ios_base::sync_with_stdio(0); cin.tie(NULL);
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define LL long long
#define mp make_pair
#define pb push_back
#define fr first
#define se second
#define endl "\n"
#define debug1 cout << "???" << endl;
#define debug2(x) cout << #x << ": " << x << endl;
const int INF = 0x3f3f3f3f;
const int N = 1e5+7;
int T, n, head[N], cnt, idcnt, m, dep[N], fa[N], siz[N], son[N], r, top[N], id[N], w[N], nw[N];
//cnt是链式前向星存图记录边 idcnt是第二遍DFS时记录树上点的新编号用 只有线段树上是用的新节点
//son[x] x的重儿子
//top[x] x所在重链的顶端节点
//id[x] x节点新编号
//w[x] x节点原来权值
//nw[x] 新编号为x的节点的权值
vector <int> G[N];
//vector存图
LL mod = (LL)1<<62;
struct SegTree
{
	LL val, add;
}t[N<<2];
struct edge
{
    int u, v, dis, nxt;
}e[N];
//如果初始边权，先用链式前向星存图后DFS0转化为vector存的图
void AddEdge(int u, int v, int dis)
{
    e[++cnt].nxt = head[u];
    e[cnt].dis = dis;
    e[cnt].v = v;
    head[u] = cnt;
}
void DFS0(int x, int f)
{
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int to = e[i].v;
        if(to == f)
            continue;
        w[to] = e[i].dis;
        G[to].pb(x);
        G[x].pb(to);
        DFS0(to, x);
    }
}
//第一遍预处理 求fa dep siz son 数组
void DFS1(int x, int f)
{
    dep[x] = dep[f]+1;
    fa[x] = f;
    siz[x] = 1;
    son[x] = 0;
    int maxson = 0;
    for(int i : G[x])
    {
        if(i == f)
            continue;
        DFS1(i, x);
        siz[x] += siz[i];
        if(siz[i] > maxson)
        {
            son[x] = i;
            maxson = siz[i];
        }
    }
}
//第二遍预处理 求top id nw 数组
void DFS2(int x, int topf)
{
    id[x] = ++idcnt;
    nw[idcnt] = w[x];
    top[x] = topf;
    if(!son[x])
        return;
    DFS2(son[x], topf);
    for(int i : G[x])
    {
        if(i == fa[x] || i == son[x])
            continue;
        DFS2(i, i);
    }
}
//线段树不必初始化，每次Build就行 一堆数组不必初始化，son DFS会初始化，其余会覆盖，0节点一直为0
void init()
{
    rep(i, 1, n)
    {
        G[i].clear();
        head[i] = 0;
    }
    cnt = idcnt = 0;
}
//线段树板子搬过来用就行
#define ls rt<<1
#define rs rt<<1|1
void PushUp(int rt)
{
    t[rt].val =(t[ls].val + t[rs].val)%mod;
}
void Build(int l, int r, int rt)
{
    t[rt].add = 0;
	if(l == r)
    {
    	//注意是nw，因为要用一段连续的
        t[rt].val = nw[l];
        return;
    }
	int mid = (l+r)>>1;
	Build(l,   mid, ls);
	Build(mid+1, r, rs);
	PushUp(rt);
}

void PushDown(int rt, int ln, int rn)
{
	t[ls].val = (t[ls].val + t[rt].add * ln) % mod;
	t[rs].val = (t[rs].val + t[rt].add * rn) % mod;
	t[ls].add = (t[ls].add + t[rt].add) % mod;
	t[rs].add = (t[rs].add + t[rt].add) % mod;
	t[rt].add = 0;
}

void Add(int L, int R, int x, int l, int r, int rt)
{
	if(L <= l && r <= R)
	{
		t[rt].val = (t[rt].val + x*(r-l+1)) % mod;
		t[rt].add = (t[rt].add + x) % mod;
		return;
	}
	int mid = (l+r) >> 1;
	PushDown(rt, mid-l+1, r-mid);
	if(L <= mid)
        Add(L, R, x, l,   mid, ls);
	if(R > mid)
        Add(L, R, x, mid+1, r, rs);
	PushUp(rt);
}
LL Query(int L, int R, int l, int r, int rt)
{
	LL res = 0;
	if(L <= l && r <= R)
	    return t[rt].val % mod;
	int mid = (l+r) >> 1;
	PushDown(rt, mid-l+1, r-mid);
	if(L <= mid)
		res = (res + Query(L, R, l,   mid, ls)) % mod;
	if(R > mid)
		res = (res + Query(L, R, mid+1, r, rs)) % mod;
	return res;
}
//如果不在同一条重链，让一直让重链顶端深度更深的点跳到父亲节点
//while结束后，就在一条重链上，深度浅的点为lca
int LCA(int u, int v)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v])
        swap(u, v);
    return u;
}
//求u到v的最短路径上点权和
//原理和求lca是一样的
//每次跳一条重链时，加上这段连续编号的区间和 【id[top[u]], id[u]】
//最后加上在同一条重链时的一段
LL QueryDis(int u, int v)
{
    LL ans = 0;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        ans += Query(id[top[u]], id[u], 1, n, 1);
        ans %= mod;
        u = fa[top[u]];
    }
    if(dep[u] > dep[v])
        swap(u, v);
    //如果 初始为边权 要减去lca 即此刻u的值
    //ans = ans - w[u];
    ans += Query(id[u], id[v], 1, n, 1);
    return ans % mod;
}
//u到v的最短路径上的点都加上val
//同上，直接用线段树的Add代替Query
void AddDis(int u, int v, int val)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        Add(id[top[u]], id[u], val, 1, n, 1);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v])
        swap(u, v);
    Add(id[u], id[v], val, 1, n, 1);
}
//在u及其子树节点加上val
//因为新的节点编号是连续的【id[u], id[u]+siz[u]-1】 直接加即可
void AddSon(int u, int val)
{
    Add(id[u], id[u]+siz[u]-1, val, 1, n, 1);
}
//求u及其子树节点权值和
//同上
LL QuerySon(int u)
{
    return Query(id[u], id[u]+siz[u]-1, 1, n, 1);
}
int main()
{
    fastio
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while(cin >> n >> m >> r >> mod)
    {
        init();
        int u, v, dis, opt, val;
        //如果是边权 用以下化为1为根 其他边权存在点上
//        rep(i, 1, n-1)
//        {
//            cin >> u >> v >> dis;
//            AddEdge(u, v, dis);
//            AddEdge(v, u, dis);
//        }
//        DFS0(1, 0);
        //如果点权 用以下直接做即可
        rep(i, 1, n)
            cin >> w[i];
        rep(i, 1, n-1)
        {
            cin >> u >> v;
            G[u].pb(v);
            G[v].pb(u);
        }
        //两边预处理以及建树
        DFS1(r, 0);
        DFS2(r, r);
        Build(1, n, 1);
        
        rep(i, 1, m)
        {
            cin >> opt;
            if(opt == 1)
            {
                cin >> u >> v >> val;
                AddDis(u, v, val);
            }
            else if(opt == 2)
            {
                cin >> u >> v;
                cout << QueryDis(u, v) << endl;
            }
            else if(opt == 3)
            {
                cin >> u >> val;
                AddSon(u, val);
            }
            else if(opt == 4)
            {
                cin >> u;
                cout << QuerySon(u) << endl;
            }
        }
    }
    return 0;
}

题目：
Occupation
大意：给一棵树，有点权，三种操作
操作1：把从x到y最短路径上的点加入集合。
操作2：如果在集合内，把x从集合中删除。
操作3：把x为根的子树加入集合。
每次操作后输出集合内权值和。

解：
加个vis数组，vis记录线段树根节点的段在 集合的情况。 vis=1说明整段在集合内，vis=0说明整段不在集合内，vis=-1说明部分在部分不在。
vis相当于一个tag，需要PushUp和PushDown，PushDown是需要的，因为可能某次直接改了一大段的vis，但是小的没变。

修改的是线段树的Query操作，因为在集合内的就不能再加了，看代码：

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize (Ofast)
#define fastio ios_base::sync_with_stdio(0); cin.tie(NULL);
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define LL long long
#define mp make_pair
#define pb push_back
#define fr first
#define se second
#define endl "\n"
#define debug1 cout << "???" << endl;
#define debug2(x) cout << #x << ": " << x << endl;
const int INF = 0x3f3f3f3f;
const int N = 1e5+7;
int T, n, idcnt, m, dep[N], fa[N], siz[N], son[N], r, top[N], id[N], w[N], nw[N], vis[N<<2];
	//vis 1 全部访问过 0 全部没访问过 -1 部分访问过
vector <int> G[N];
LL mod = (LL)1<<62, ans;
struct SegTree
{
	LL val, add;
}t[N<<2];

void DFS1(int x, int f)
{
    dep[x] = dep[f]+1;
    fa[x] = f;
    siz[x] = 1;
    son[x] = 0;
    int maxson = 0;
    for(int i : G[x])
    {
        if(i == f)
            continue;
        DFS1(i, x);
        siz[x] += siz[i];
        if(siz[i] > maxson)
        {
            son[x] = i;
            maxson = siz[i];
        }
    }
}
void DFS2(int x, int topf)
{
    id[x] = ++idcnt;
    nw[idcnt] = w[x];
    top[x] = topf;
    if(!son[x])
        return;
    DFS2(son[x], topf);
    for(int i : G[x])
    {
        if(i == fa[x] || i == son[x])
            continue;
        DFS2(i, i);
    }
}
void init()
{
    rep(i, 1, n)
    {
        G[i].clear();

    }
    idcnt = ans = 0;
}
#define ls rt<<1
#define rs rt<<1|1
void PushUp(int rt)
{
    t[rt].val =(t[ls].val + t[rs].val)%mod;
    if(vis[ls] == 0 && vis[rs] == 0)
        vis[rt] = 0;
    //注意这三种情况
    else if(vis[ls] == 1 && vis[rs] == 1)
        vis[rt] = 1;
    else
        vis[rt] = -1;
}
void Build(int l, int r, int rt)
{
    t[rt].add = vis[rt] = 0;
	if(l == r)
    {
        t[rt].val = nw[l];
        return;
    }
	int mid = (l+r)>>1;
	Build(l,   mid, ls);
	Build(mid+1, r, rs);
	PushUp(rt);
}

void PushDown(int rt, int ln, int rn)
{
	t[ls].val = (t[ls].val + t[rt].add * ln) % mod;
	t[rs].val = (t[rs].val + t[rt].add * rn) % mod;
	t[ls].add = (t[ls].add + t[rt].add) % mod;
	t[rs].add = (t[rs].add + t[rt].add) % mod;
	t[rt].add = 0;
	//只有vis为1或者0才需要处理，不然-1是PushUp上去的，下面肯定已经处理好了
	if(vis[rt] == 1)
        vis[ls] = vis[rs] = 1;
    else if(vis[rt] == 0)
        vis[ls] = vis[rs] = 0;
}

LL Query(int L, int R, int l, int r, int rt)
{
    //printf("L %d R %d l %d r %d rt %d\n", L, R, l, r, rt);
	LL res = 0;
	if(L <= l && r <= R)
    {
        if(vis[rt] == 1)
            return 0;
        if(vis[rt] == 0)
        {
        	//加上了记得改为在集合里
            vis[rt] = 1;
            return t[rt].val % mod;
        }
    }
	int mid = (l+r) >> 1;
	PushDown(rt, mid-l+1, r-mid);
	if(L <= mid)
		res = (res + Query(L, R, l,   mid, ls)) % mod;
	if(R > mid)
		res = (res + Query(L, R, mid+1, r, rs)) % mod;
    PushUp(rt);
	return res;
}
int QueryVis(int x, int l, int r, int rt)
{
    if(vis[rt] == 1)
        return 1;
    if(vis[rt] == 0)
        return 0;
    int mid = (l+r) >> 1;
    PushDown(rt, mid-l+1, r-mid);
    if(x <= mid)
        return QueryVis(x, l,   mid, ls);
    if(x > mid)
        return QueryVis(x, mid+1, r, rs);
}
void DelVis(int x, int l, int r, int rt)
{
    if(l == r)
    {
        vis[rt] = 0;
        return;
    }
    int mid = (l+r) >> 1;
    PushDown(rt, mid-l+1, r-mid);
    if(x <= mid)
        DelVis(x, l,   mid, ls);
    if(x > mid)
        DelVis(x, mid+1, r, rs);
    PushUp(rt);
}

LL QueryDis(int u, int v)
{
    LL ans = 0;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        ans += Query(id[top[u]], id[u], 1, n, 1);
        ans %= mod;
        u = fa[top[u]];
    }
    if(dep[u] > dep[v])
        swap(u, v);
    ans += Query(id[u], id[v], 1, n, 1);
    return ans % mod;
}

LL QuerySon(int u)
{
    return Query(id[u], id[u]+siz[u]-1, 1, n, 1);
}
int main()
{
    fastio
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin >> T;
    while(T--)
    {
        cin >> n;
        init();
        int u, v, val, opt;
        rep(i, 1, n)
            cin >> w[i];
        rep(i, 1, n-1)
        {
            cin >> u >> v;
            G[u].pb(v);
            G[v].pb(u);
        }
        DFS1(1, 0);
        DFS2(1, 1);
        Build(1, n, 1);
        cin >> m;
        rep(i, 1, m)
        {
            cin >> opt;
            if(opt == 1)
            {
                cin >> u >> v;
                ans += QueryDis(u, v);
            }
            else if(opt == 2)
            {
                cin >> u;
                if(QueryVis(id[u], 1, n, 1))
                {
                    ans -= w[u];
                    DelVis(id[u], 1, n, 1);
                }
            }
            else if(opt == 3)
            {
                cin >> u;
                ans += QuerySon(u);
            }
            cout << ans << endl;
        }
    }
    return 0;
}