VI.【模板】点分树 | 震波
我们之前讲过一个叫做淀粉徐的东西，但就跟dfs序一样，把树压成序列，总会损失一些信息。有没有方法能够完整地维护出来淀粉质的信息呢？
还真有。
我们看到在对于某个点淀粉质时，它的所有子树，都会拥有一个下层的分治节点。
我们看到淀粉质的代码：
void solve(int x){
vis[x]=true;
for(auto y:v[x])if(!vis[y])ROOT=0,SZ=sz[y],getroot(y,x),solve(ROOT);
}
则ROOT便是x的下层分治节点。因此，我们另外建一棵树，在这颗树里面，连边\((x,ROOT)\)。
我们把这颗树叫做点分数点分树（centriod decomposition tree, cdt（英文我瞎写的）
-
它的深度是\(\log n\)级别的，即为普通淀粉质的深度。
-
每一个点在点分树上的子树中，包含了它原树子树中所有的节点。但是很明显，父子关系被完全打乱了，因此例如求距离时，必须要从原树上求。
通过这种数据结构，我们便可以将淀粉质的全过程离线下来，这样就不用每次询问都再跑一遍淀粉质了。
例如这道题。单点修改，块（？）求和。应该怎么做呢？
我们可以对于点分树上每个点，以到该点的距离（注意是原树上距离）为下标，对于子树中所有点维护一种数据结构，支持前缀求和，单点修改。
显然这是线段树的活，但是像我这样人傻常数大的代码要是敢写这个是肯定爆炸的（实际上也的确爆炸了）。换成用vector实现的树状数组即可通过。在询问时，在该点上前缀求和即可。
但是这样显然有问题——它父亲方向的所有点，都没有被计入。怎么办呢？
我们必须往父亲方向跳，然后再在父亲这里的动态开点线段树上统计一下。但这又有两个问题——一是父亲的父亲需要考虑，二是该点自身子树被算了两次。问题一可以通过不断跳父亲解决，那么问题二呢？
我们把之前的树状数组叫做“\(rtsn\)”，然后再开一颗叫做“\(rtfa\)”，表示子树中所有点到（点分树上的）父亲的（原树上的）距离。在每个点处挖掉\(rtfa\)上的前缀和即可。
至于修改吗，也是不断跳父亲，在树状数组上对应位置修改即可。
复杂度的话，树状数组一个\(\log\)，然后点分树树深又是一个\(\log\)，故总复杂度\(O(n\log^2n)\)。
代码（树状数组可卡过，如果换成动态开点线段树就是TLE70）：
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int n,m,val[100100],fa[100100],dep[200100],in[100100],tot,mn[200100][20],LG[200100];
namespace Tree{
vector<int>v[100100];
int sz[100100],SZ,msz[100100],ROOT;
bool vis[100100];
void getsz(int x,int fa){
sz[x]=1;
for(auto y:v[x])if(!vis[y]&&y!=fa)getsz(y,x),sz[x]+=sz[y];
}
void getroot(int x,int fa){
sz[x]=1,msz[x]=0;
for(auto y:v[x])if(!vis[y]&&y!=fa)getroot(y,x),sz[x]+=sz[y],msz[x]=max(msz[x],sz[y]);
msz[x]=max(msz[x],SZ-sz[x]);
if(msz[x]<msz[ROOT])ROOT=x;
}
void solve(int x){
getsz(x,0);
vis[x]=true;
for(auto y:v[x]){
if(vis[y])continue;
ROOT=0,SZ=sz[y],getroot(y,0),fa[ROOT]=x,solve(ROOT);
}
}
void getural(int x,int fa){
mn[++tot][0]=x,in[x]=tot;
for(auto y:v[x])if(y!=fa)dep[y]=dep[x]+1,getural(y,x),mn[++tot][0]=x;
}
}
int MIN(int i,int j){
return dep[i]<dep[j]?i:j;
}
int LCA(int i,int j){
if(i>j)swap(i,j);
int k=LG[j-i+1];
return MIN(mn[i][k],mn[j-(1<<k)+1][k]);
}
int DIS(int i,int j){
return dep[i]+dep[j]-dep[LCA(in[i],in[j])]*2;
}
namespace CDT{//centriod decomposition tree
vector<int>v[100100],dis[100100];
#define mid ((l+r)>>1)
struct FenwickTree:vector<int>{
void ADD(int x,int y){
while(x<size())(*this)[x]+=y,x+=x&-x;
}
int SUM(int x){
int sum=0;
while(x)sum+=(*this)[x],x-=x&-x;
return sum;
}
}rtfa[100100],rtsn[100100];
struct SegTree{
int lson,rson,sum;
}seg[10001000];
void change(int x,int y){
int u=x;
while(u){
int td=DIS(u,x);
// printf("(%d,%d):%d\n",u,x,td);
td=lower_bound(dis[u].begin(),dis[u].end(),td)-dis[u].begin()+1;
// printf("SF::%d:(%d,%d):%d\n",x,u,td,y-val[x]);
rtsn[u].ADD(td,y-val[x]);
if(!fa[u])break;
td=DIS(fa[u],x);
// printf("(%d,%d):%d\n",fa[u],x,td);
td=lower_bound(dis[fa[u]].begin(),dis[fa[u]].end(),td)-dis[fa[u]].begin()+1;
// printf("FA::%d:(%d,%d):%d\n",x,u,td,y-val[x]);
rtfa[u].ADD(td,y-val[x]);
u=fa[u];
}
val[x]=y;
}
int ask(int x,int y){
int u=x,res=0;
while(u){
int td=y-DIS(u,x);
td=upper_bound(dis[u].begin(),dis[u].end(),td)-dis[u].begin();
// printf("SF::%d:(%d,%d)\n",x,u,td);
res+=rtsn[u].SUM(td);
if(!fa[u])break;
td=y-DIS(fa[u],x);
td=upper_bound(dis[fa[u]].begin(),dis[fa[u]].end(),td)-dis[fa[u]].begin();
// printf("FA::%d:(%d,%d)\n",x,u,td);
res-=rtfa[u].SUM(td);
u=fa[u];
}
return res;
}
void getdis(int x,int z){
dis[z].push_back(DIS(x,z));
for(auto y:v[x])getdis(y,z);
}
void init(){
int RT=0;
for(int i=1;i<=n;i++)if(fa[i])v[fa[i]].push_back(i);else RT=i;
for(int i=1;i<=n;i++)dis[i].push_back(0),getdis(i,i),sort(dis[i].begin(),dis[i].end()),dis[i].resize(unique(dis[i].begin(),dis[i].end())-dis[i].begin());
for(int i=1;i<=n;i++){
rtsn[i].resize(dis[i].size()+1);
if(fa[i])rtfa[i].resize(dis[fa[i]].size()+1);
}
// for(int i=1;i<=n;i++){for(auto x:dis[i])printf("%d ",x);puts("");}
for(int i=1,x;i<=n;i++)x=val[i],val[i]=0,change(i,x);
}
}
void read(int &x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
read(n),read(m);
for(int i=1;i<=n;i++)read(val[i]);
for(int i=1,x,y;i<n;i++)read(x),read(y),Tree::v[x].push_back(y),Tree::v[y].push_back(x);
Tree::msz[0]=0x3f3f3f3f,Tree::SZ=n,Tree::getroot(1,0),Tree::solve(Tree::ROOT);
// for(int i=1;i<=n;i++)printf("%d ",fa[i]);puts("");
Tree::getural(1,0);
// for(int i=1;i<=n;i++)printf("%d ",dep[i]);puts("");
// for(int i=1;i<=tot;i++)printf("%d ",mn[i][0]);puts("");
for(int i=2;i<=tot;i++)LG[i]=LG[i>>1]+1;
for(int j=1;j<=LG[tot];j++)for(int i=1;i+(1<<j)-1<=tot;i++)mn[i][j]=MIN(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
CDT::init();
for(int i=1,x,y,z,las=0;i<=m;i++){
read(x),read(y),read(z),y^=las,z^=las;
if(x==1)CDT::change(y,z);
else printf("%d\n",las=CDT::ask(y,z));
}
return 0;
}