【loj#139】树链剖分

#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

样例输出

数据范围与提示

对于 $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;

巴特西