CF916E 题解

CF916E Jamie and Tree

先贴个代码，详细说明以后有时间再来填，代码中有很详细的注释，看不懂可以先私信我。

// Problem: CF916E Jamie and Tree
// Memory Limit: 250 MB
// Time Limit: 2500 ms

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 50;
#define int long long
int tot = 0,start[MAXN];
int n,Q,A[MAXN],dfn_N[MAXN],now = 0,root = 1;

struct Node {
    int dfn,siz,fa,tp,son,dep;
} N[MAXN];

struct Edge {
    int next,to;
    void add(int u,int v) {to = v , next = start[u] , start[u] = tot;}
} edge[MAXN * 2];

struct SegmentTree {
    int l,r,sum,laz;
} T[MAXN * 4];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int DFS1(int x,int from) {
    N[x].siz = 1 , N[x].son = 0 , N[x].fa = from;
    N[x].dep = N[from].dep + 1;
    for(int i = start[x] ; i ; i = edge[i].next) {
        int to = edge[i].to;
        if(to == from) continue;
        int v = DFS1(to , x);
        if(v > N[N[x].son].siz) N[x].son = to;
        N[x].siz += v;
    }
    return N[x].siz;
}

void DFS2(int x,int top) {
    N[x].tp = top; N[x].dfn = ++now; dfn_N[now] = x;
    if(N[x].son) DFS2(N[x].son , top);
    for(int i = start[x] ; i ; i = edge[i].next) {
        int to = edge[i].to;
        if(to == N[x].fa || to == N[x].son) continue;
        DFS2(to , to);
    }
    return ;
}

void build_Tree(int x,int l,int r) {
    T[x].l = l , T[x].r = r;
    T[x].laz = 0; T[x].sum = 0;
    if(l == r) {T[x].sum = A[dfn_N[l]] ; return ;}
    int mN = (l + r) >> 1;
    build_Tree(x << 1 , l , mN);
    build_Tree(x << 1 | 1 , mN + 1 , r);
    T[x].sum = T[x << 1].sum + T[x << 1 | 1].sum;
    return ;
}

int GetLCA(int x,int y) { // 推荐树链剖分求LCA，毕竟都打好了树链剖分....
    while(N[x].tp != N[y].tp) {
        if(N[N[x].tp].dep < N[N[y].tp].dep) swap(x , y);
        x = N[N[x].tp].fa;
    } 
    if(N[x].dep < N[y].dep) return x;
    return y;
}

int pdLCA(int x,int y) { //手动画重点，这是这个题目最难的地方！密集注释来临
    if( N[x].dep > N[y].dep ) swap(x , y);//手动使得x的深度小于等于y的深度
    if(GetLCA(x,y) == x) { //倘若x是y的祖先
        if(N[root].dfn >= N[y].dfn && N[root].dfn <= N[y].dfn + N[y].siz - 1) return y;
        //倘若当前根root在原来的树中是y的儿子，自己画图就知道，那么肯定离当前根越近的就是祖先，所以返回y
        //如果不是上面的情况，也就是意味着当前根root可能是夹在 x，y中间 或者 x,y在原本的树中都是当前根的儿子
        if(GetLCA(x,root) == x) return GetLCA(y,root);
        //当前根root夹在 x,y中间的话，返回y跟root的LCA，这个可以画图，不可以直接返回root
        return x;//如果是说当前根是 x 的祖先，直接返回 x 
    }
    //下面的情况都是 x,y 不是祖先关系的情况
    if(N[root].dfn >= N[x].dfn && N[root].dfn <= N[x].dfn + N[x].siz - 1) return x; //当前根在x的子树中
    if(N[root].dfn >= N[y].dfn && N[root].dfn <= N[y].dfn + N[y].siz - 1) return y; //当前根在y的子树中
    if( (GetLCA(x,root) == root && GetLCA(x,y) == GetLCA(y,root)) || 
        /*上面这一行的意思是，root是x的祖先，并且x，y在原来的树中的LCA是 y 和 root 的LCA，那么应该返回根。
          其实用画图说明这个if，则是说，x,y 一个处于当前根的子树中，
          另外一个呢并不处于当前根的子树中，那么就意味着 x,y被 当前根“隔开了”，所以返回root
          下面一行同理。
        */
        (GetLCA(y,root) == root && GetLCA(x,y) == GetLCA(x,root)) )return root;
    if(GetLCA(x,root) == GetLCA(y,root)) return GetLCA(x,y);//这个就表明，x,y均不是root子树中的节点，就没有影响
    if(GetLCA(x,y) != GetLCA(x,root)) return GetLCA(x,root);
    /*这里就是说，x到y的路径中，与当前 root 到 x 的路径的交集只有x 到 LCA(x,root) 这一段，可以画图进行理解*/
    return GetLCA(y ,root);//同理
}

void ad(int x,int k) {
    T[x].sum += (T[x].r - T[x].l + 1) * k;
    T[x].laz += k;
    return ;
}

void pushdown(int x) {
    if(T[x].laz == 0) return ;
    ad(x << 1 , T[x].laz);
    ad(x << 1 | 1 , T[x].laz);
    T[x].laz = 0;
    return ;
}

void change(int x,int l,int r,int k) {//线段树区间修改，这个应该都会
    if(T[x].l >= l && T[x].r <= r) {
        ad(x , k);
        return ;
    }
    pushdown(x);
    int mid = (T[x].l + T[x].r) >> 1;
    if(l <= mid) change(x << 1 , l , r , k);
    if(r >  mid) change(x << 1 | 1 , l , r , k);
    T[x].sum = T[x << 1].sum + T[x << 1 | 1].sum;
    return ;
}

int GetAns(int x,int l,int r) { //线段树区间求和，这个应该都会
    if(T[x].l >= l && T[x].r <= r) return T[x].sum ;
    int mid = (T[x].l + T[x].r) >> 1 , sum = 0;
    pushdown(x);
    if(l <= mid) sum += GetAns(x << 1 , l , r );
    if(r  > mid) sum += GetAns(x << 1 | 1 , l , r );
    return sum;
}

int GetFa(int x,int y) { //寻找某个点 x 的一个儿子，使得这个儿子离x距离为1而且是y的祖先  
    while(N[x].tp != N[y].tp) {
        if(N[N[x].tp].dep < N[N[y].tp].dep) swap(x,y);
        if(N[N[x].tp].fa == y) return N[x].tp;
        x = N[N[x].tp].fa;
    }
    if(N[x].dep > N[y].dep) swap(x,y);
    return N[x].son;
}

signed main() {
    n = read(); Q = read();
    for(int i = 1 ; i <= n ; i ++) A[i] = read();
    for(int i = 2 ; i <= n ; i ++) {
        int u = read() , v = read();
        edge[++tot].add(u,v);
        edge[++tot].add(v,u);
    }
    DFS1(1,0);DFS2(1,1);root = 1;
    build_Tree(1 , 1 , n);
    while(Q --) {
        int op = read();
        if(op == 1) root = read(); //直接换根
        if(op == 2) {
            int u = read() ,v = read() , D = read();
            int x = pdLCA(u , v);
            if(x == root) change(1, 1 , n , D);//表示是就是给出的点是根，直接整棵树修改
            else if(x == GetLCA(root,x)) { //表示是在1到当前根的路径上
                change(1 , 1 , n , D);
                int z = GetFa(x , root);
                change(1, N[z].dfn , N[z].dfn + N[z].siz - 1 , -D);//要还原
            }
            else change(1 , N[x].dfn, N[x].dfn + N[x].siz - 1 , D); //表示是在1的不同子树外，可以直接处理                
        }
        if(op == 3) {
            int Ans = 0;
            int x = read();
            if(x == root) Ans = GetAns(1, 1 , n );//表示是就是给出的点是根，直接整棵树修改
            else if(GetLCA(x,root) == x) { //表示是在1到当前根的路径上
                Ans = GetAns(1 , 1 , n);
                int z = GetFa(x , root);
                Ans -= GetAns(1, N[z].dfn , N[z].dfn + N[z].siz - 1);
            }
            else  Ans = GetAns(1 , N[x].dfn,N[x].dfn + N[x].siz - 1); //表示是在1的不同子树外，可以直接处理
            cout << Ans << endl;
        }
    }
    return 0;
}