#139. 树链剖分
题目描述
这是一道模板题。
给定一棵 $n$个节点的树，初始时该树的根为 111 号节点，每个节点有一个给定的权值。下面依次进行 $m$ 个操作，操作分为如下五种类型：
换根：将一个指定的节点设置为树的新根。
修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。
修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。
询问路径：询问某条路径上节点的权值和。
询问子树：询问某个子树内节点的权值和
输入格式
第一行为一个整数 n，表示节点的个数。
第二行 n 个整数表示第 iii 个节点的初始权值 $a_i$。
第三行 n−1 个整数，表示 i+1i+1i+1 号节点的父节点编号$ fi+1 (1⩽fi+1⩽n)f_{i+1}\ (1 \leqslant f_{i+1} \leqslant n)fi+1 (1⩽fi+1⩽n)。$
第四行一个整数 m，表示操作个数。
接下来 m 行，每行第一个整数表示操作类型编号：$(1⩽u,v⩽n)(1 \leqslant u, v \leqslant n)(1⩽u,v⩽n)$
若类型为 111，则接下来一个整数 u，表示新根的编号。
若类型为 222，则接下来三个整数 u,v,ku,v,ku,v,k，分别表示路径两端的节点编号以及增加的权值。
若类型为 333，则接下来两个整数 u,ku,ku,k，分别表示子树根节点编号以及增加的权值。
若类型为 444，则接下来两个整数 u,vu,vu,v，表示路径两端的节点编号。
若类型为 555，则接下来一个整数 u，表示子树根节点编号。
输出格式
对于每一个类型为 444 或 555 的操作，输出一行一个整数表示答案。
样例
样例输入
6
1 2 3 4 5 6
1 2 1 4 4
6
4 5 6
2 2 4 1
5 1
1 4
3 1 2
4 2 5样例输出
15
24
19数据范围与提示
对于 $100%100\%100%$ 的数据，$1⩽n,m,k,ai⩽1051\leqslant n,m,k,a_i\leqslant 10^51⩽n,m,k,ai⩽105$。数据有一定梯度。
题意：树链加，子树加，需要支持换根，查询树链和，子树和
题解：
树链剖分模板，树链加和查询直接树链剖分即可，
注意到树链剖分有个很方便的性质就是链剖的序列其实也是dfs序，记录一个点的序列上起点和终点就可以顺便维护子树，
换根的话分类讨论一下，一直以1号点为根，对树链的修查无影响，考虑子树：
假设访问u号点，在以1号点为根的形态下：
当前根rt，如果u==rt则u的子树为整个以1为根的树，
如果rt是u的子树里的节点，那么u所代表的的子树就是整个子树 - rt的祖先里u的儿子的 子树 ，
如果rt不是u的子树里的节点，那么u的子树就是以1为根时u的子树；
这样操作后也是区间，可以和前两个一起维护；
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#define ls (k<<1)
#define rs (k<<1|1)
#define Run(i,l,r) for(int i=l;i<=r;i++)
#define Don(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=;
int n,m,o,hd[N],tp[N],st[N],ed[N],idx,son[N],fa[N],w[N],sz[N],dep[N],root;//
ll val[N],sum[N<<],ly[N<<];//
struct Edge{int v,nt;}E[N<<]; //
char gc(){
static char*p1,*p2,s[];
if(p1==p2)p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}//
int rd(){
int x=,f=; char c=gc();
while(c<''||c>''){if(c=='-')f=-;c=gc();}
while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'',c=gc();}
return x*f;
}//
void adde(int u,int v){
E[o]=(Edge){v,hd[u]};hd[u]=o++;
E[o]=(Edge){u,hd[v]};hd[v]=o++;
}//
void dfsA(int u,int F){
dep[u]=dep[F]+;
son[u]=; sz[u]=;
for(int i=hd[u];~i;i=E[i].nt){
int v=E[i].v;
if(v==F)continue;
dfsA(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
}//
void dfsB(int u,int T){
tp[u]=T; val[st[u]=++idx]=w[u];
if(son[u])dfsB(son[u],T);
for(int i=hd[u];~i;i=E[i].nt){
int v=E[i].v;
if(v==son[u]||v==fa[u])continue;
dfsB(v,v);
}
ed[u]=idx;
}//
void pushup(int k){sum[k]=sum[ls]+sum[rs];}//
void mfy(int k,int l,int r,ll v){sum[k]+=v*(r-l+);ly[k]+=v;}//
void pushdown(int k,int l,int r){
if(ly[k]){
int mid=(l+r)>>;
mfy(ls,l,mid,ly[k]);
mfy(rs,mid+,r,ly[k]);
ly[k]=;
}
}//
void build(int k,int l,int r){
if(l==r){sum[k]=val[l];ly[k]=;return;}
int mid=(l+r)>>;
build(ls,l,mid);
build(rs,mid+,r);
pushup(k);
}//
void update(int k,int l,int r,int x,int y,ll v){
if(l==x&&r==y)mfy(k,l,r,v);
else {
pushdown(k,l,r);
int mid=(l+r)>>;
if(y<=mid)update(ls,l,mid,x,y,v);
else if(x>mid)update(rs,mid+,r,x,y,v);
else update(ls,l,mid,x,mid,v) , update(rs,mid+,r,mid+,y,v);
pushup(k);
}
}//
ll query(int k,int l,int r,int x,int y){
if(l==x&&r==y)return sum[k];
else {
pushdown(k,l,r);
int mid=(l+r)>>;
if(y<=mid)return query(ls,l,mid,x,y);
else if(x>mid)return query(rs,mid+,r,x,y);
else return query(ls,l,mid,x,mid) + query(rs,mid+,r,mid+,y);
}
}//
int child(int u,int v){
while(tp[u]!=tp[v]){
u=tp[u];
if(fa[u]==v)return u;
u=fa[u];
}
return son[v];
}//
void update1(int u,int v,int x){
while(tp[u]!=tp[v]){
if(dep[tp[u]]<dep[tp[v]])swap(u,v);
update(,,n,st[tp[u]],st[u],x);
u=fa[tp[u]];
}
if(dep[u]<dep[v])swap(u,v);
update(,,n,st[v],st[u],x);
}//
void update2(int u,int x){
if(u==root){update(,,n,,n,x);}
else if(st[u]<=st[root]&&ed[root]<=ed[u]){
int t = child(root,u);
update(,,n,,n,x);
update(,,n,st[t],ed[t],-x);
}
else{update(,,n,st[u],ed[u],x);}
}//
void query1(int u,int v){
ll ret=;
while(tp[u]!=tp[v]){
if(dep[tp[u]]<dep[tp[v]])swap(u,v);
ret += query(,,n,st[tp[u]],st[u]);
u=fa[tp[u]];
}
if(dep[u]<dep[v])swap(u,v);
ret += query(,,n,st[v],st[u]);
printf("%lld\n",ret);
}//
void query2(int u){
ll ret=;
if(u==root)ret=query(,,n,,n);
else if(st[u]<=st[root]&&ed[root]<=ed[u]){
int t = child(root,u);
ret += query(,,n,,n);
ret -= query(,,n,st[t],ed[t]);
}
else{ret = query(,,n,st[u],ed[u]);}
printf("%lld\n",ret);
}//
int main(){
//freopen("loj139.in","r",stdin);
//freopen("loj139.out","w",stdout);
n=rd();
for(int i=;i<=n;i++)w[i]=rd(),hd[i]=-;
for(int i=;i<=n;i++)adde(fa[i]=rd(),i);
dfsA(root=,);dfsB(,);
build(,,n);
m=rd();
for(int i=,u,v,x;i<=m;i++){
int op=rd();
if(op==)root=rd();
else if(op==){u=rd();v=rd();x=rd();update1(u,v,x);}
else if(op==){u=rd();x=rd();update2(u,x);}
else if(op==){u=rd();v=rd();query1(u,v);}
else {u=rd();query2(u);}
}
return ;
}//by tkys_Austin;