换根

这是一道模板题。

给定一棵

换根：将一个指定的节点设置为树的新根。
修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。
修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。
询问路径：询问某条路径上节点的权值和。
询问子树：询问某个子树内节点的权值和。

sol：

嗯，考虑换根

首先我们可以知道，换根对链操作没有影响

然后我们来处理子树问题

1.如果根就是当前的询问节点$(root = x)$就相当于询问/修改整棵树

2.如果根在当前节点的子树里，我们考虑子树的定义，子树就是$x$和$x$的“下面”部分（我们定义“根向$x$”为向下，“x到根”为向上）

由这一条，我们可以从根往$x$找，找到在$x$底下那个点，修改那个点的子树以外的点即可，这一步可以倍增来找

3.其他情况，就是原来的子树操作

顺便：

如果记一个点$x$的dfs序为$dfn_x$

一个点的子树的dfs序在$[dfn_x,dfn_x + size_x - 1]$这个区间里

#include<bits/stdc++.h>
#define int long long
#define LL long long
using namespace std;
inline LL read()
{
    LL x = 0,f = 1;char ch = getchar();
    for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f;
    for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0';
    return x * f;
}
const int maxn = 200010;
int n,m,rt;
int first[maxn],to[maxn << 1],nx[maxn << 1],cnt;
int fa[maxn],dep[maxn],pos[maxn],bl[maxn],size[maxn],dfn;
int va[maxn];
inline void add(int u,int v)
{
    to[++cnt] = v;
    nx[cnt] = first[u];
    first[u] = cnt;
}
int anc[maxn][22];
inline void ins(int u,int v){add(u,v);add(v,u);}
inline void dfs1(int x)
{
    for(int i=1;i<=21;i++)
        anc[x][i] = anc[anc[x][i - 1]][i - 1];
    size[x] = 1;
    for(int i=first[x];i;i=nx[i])
    {
        if(to[i] != fa[x])
        {
            fa[to[i]] = anc[to[i]][0] = x;
            dep[to[i]] = dep[x] + 1;
            dfs1(to[i]);size[x] += size[to[i]];
        }
    }
}
inline int get_anc(int x,int y)
{
    int t = dep[x] - y;
    for(int i=21;~i;i--)
        if(t & (1 << i))x = anc[x][i];
    return x;
}
inline void dfs2(int x,int col)
{
    pos[x] = ++dfn;bl[x] = col;
    int k = 0;
    for(int i=first[x];i;i=nx[i])
        if(to[i] != fa[x] && size[to[i]] > size[k])k = to[i];
    if(!k)return;
    dfs2(k,col);
    for(int i=first[x];i;i=nx[i])
        if(to[i] != fa[x] && to[i] != k)dfs2(to[i],to[i]);
}
#define ls (x << 1)
#define rs ((x << 1) | 1)
int seg[maxn << 2],tag[maxn << 2];
inline void pushdown(int x,int l,int r)
{
    if(tag[x])
    {
        int mid = (l + r) >> 1;
        tag[ls] += tag[x];tag[rs] += tag[x];
        seg[ls] += tag[x] * (mid - l + 1);seg[rs] += tag[x] * (r - mid);
        tag[x] = 0;
    }
}
inline void update(int x,int l,int r,int L,int R,int v)
{
    if(L <= l && r <= R)
    {
        seg[x] += (r - l + 1) * v;
        tag[x] += v;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(x,l,r);
    if(L <= mid)update(ls,l,mid,L,R,v);
    if(R > mid)update(rs,mid + 1,r,L,R,v);
    seg[x] = seg[ls] + seg[rs];
}
inline int query(int x,int l,int r,int L,int R)
{
    if(L <= l && r <= R)return seg[x];
    int mid = (l + r) >> 1,ans = 0;
    pushdown(x,l,r);
    if(L <= mid)ans = ans + query(ls,l,mid,L,R);
    if(R > mid)ans = ans + query(rs,mid + 1,r,L,R);
    return ans;
}
inline void mod_chain(int x,int y,int v)
{
    while(bl[x] != bl[y])
    {
        if(dep[bl[x]] < dep[bl[y]])swap(x,y);
        update(1,1,n,pos[bl[x]],pos[x],v);x = fa[bl[x]];
    }
    if(pos[x] > pos[y])swap(x,y);
    update(1,1,n,pos[x],pos[y],v);
}
inline int q_chain(int x,int y)
{
    int ans = 0;
    while(bl[x] != bl[y])
    {
        if(dep[bl[x]] < dep[bl[y]])swap(x,y);
        ans += query(1,1,n,pos[bl[x]],pos[x]);x = fa[bl[x]];
    }
    if(pos[x] > pos[y])swap(x,y);
    ans += query(1,1,n,pos[x],pos[y]);
    return ans;
}
inline int lca(int x,int y)
{
    while(bl[x] != bl[y])
    {
        if(dep[bl[x]] < dep[bl[y]])swap(x,y);
        x = fa[bl[x]];
    }
    return dep[x] > dep[y] ? y : x;
}
inline void q_subtree(int x)
{
    int type = lca(rt,x);
    if(rt == x)
    {
        printf("%lld
",query(1,1,n,1,n));
        return;
    }
    else if(type == x)
    {
        int v = get_anc(rt,dep[x] + 1);
        printf("%lld
",query(1,1,n,pos[v] + size[v],n) + query(1,1,n,1,pos[v] - 1));
        return ;
    }
    else
    {
        printf("%lld
",query(1,1,n,pos[x],pos[x] + size[x] - 1));
        return;
    }
}
inline void mod_subtree(int x,int va)
{
    int type = lca(rt,x);
    if(rt == x)
    {
        update(1,1,n,1,n,va);
        return;
    }
    else if(type == x)
    {
        int v = get_anc(rt,dep[x] + 1);
        update(1,1,n,pos[v] + size[v],n,va);
        update(1,1,n,1,pos[v] - 1,va);
        return ;
    }
    else
    {
        update(1,1,n,pos[x],pos[x] + size[x] - 1,va);
        return;
    }
}
signed main()
{
    n = read();
    for(int i=1;i<=n;i++)va[i] = read();
    for(int i=2;i<=n;i++)
    {
        int fi = read();
        ins(fi,i);
    }m = read();
    dfs1(rt = 1);dfs2(rt,rt);
    for(int i=1;i<=n;i++)update(1,1,n,pos[i],pos[i],va[i]);
    while(m--)
    {
        int opt = read();
        if(opt == 1)rt = read();
        else if(opt == 2)
        {
            int p1 = read(),p2 = read(),v = read();
            mod_chain(p1,p2,v);
        }
        else if(opt == 3)
        {
            int x = read(),va = read();
            mod_subtree(x,va);
        }
        else if(opt == 4)
        {
            int l = read(),r = read();
            printf("%lld
",q_chain(l,r));
        }
        else
        {
            int x = read();
            q_subtree(x);
        }
    }
}

View Code

upd：换完根后，u,v 实际上的 lca_real(u,v) 是 lca(u,v), lca(u,root),lca(v,root) 中深度最大的那个