题解 P6329 【【模板】点分树 | 震波】

tzc_wk · 2021-01-10 00:23:14 · 题解

首先我们知道，单次询问，树上路径的问题可以用点分治解决。

但如果加上什么 q 次询问之类的东西怎么办呢？比如说这题。

显然每次都跑一遍点分治时间复杂度肯定吃不消。

考虑把点分治的过程离线下来，将当前树的重心与上一层的树的重心连边，这样就可以得到一棵树，我们称之为“点分树”

比如说我们有如下图所示的树：

建出点分树来如下图所示：

很明显，我们建出的点分树与原树几乎没有联系，父子关系完全被打乱了，也无法通过两点在点分树上的距离算出它们在原树上的距离。甚至有可能某两点在点分树上是父子关系，在原树上相隔十万八千里，或者某两点在原树上是父子关系，在点分树上相隔十万八千里（当然只是相对来说）。

那么这棵树对于我们做题有什么帮助呢？

有的问题我们不是非常关心树的形态特点，比如路径问题，联通块问题，寻找关键点问题等等，以路径问题为例，我们不一定非得查到 p,q 的 LCA 才可以处理 p,q 的路径信息，相反，我们可以随便从这个路径上寻找一个分割点 t，只要我们可以快速的处理 p 到 t 和 q 到 t 的信息，我们就可以处理 p 到 q 的信息。

而点分树恰恰就是对原树做了这样的映射。

它有以下性质：

它的高度与点分治的深度一样，只有 \log n 级别，这个性质很关键，由于它的高度只有 \log n，所以我们可以搞出各种各样在一般树论里过不去的暴力做法，比如说对每个点开个包含子树中所有点的 vector，空间复杂度也只有。
对于任意两点 u,v，唯一可以确定的是 u,v 在点分树上的 LCA 一定在 u\to v 的路径上。换句话说，dis(u,v)=dis(u,lca)+dis(lca,v)。

回到这题来，我们要求 \sum\limits_{dis(x,y)\leq k}a_y。

考虑枚举 x,y 在点分树上的 LCA z（这显然是 \log n 级别的），根据上面的推论有 dis(x,y)=dis(x,z)+dis(y,z)。

故 ans=\sum\limits_{dis(x,z)+dis(z,y)\leq k\& LCA(x,y)=z}a_y=\sum\limits_{dis(z,y)\leq k-dis(x,z)\&LCA(x,y)=z}a_y

考虑什么样的 y 满足 LCA(x,y)=z，显然符合要求 y 组成的集合就是 z 的子树抠掉 z 在 x 方向上的儿子 s 的子树。而我们要求这个点集中到 z 的距离 \leq k-dis(x,z) 的点权和。显然可以拿 z 的子树内到 z 的距离 \leq k-dis(x,z) 的点权和 - s 子树中到 z 的距离 \leq k-dis(x,z) 的点权和。

对每个点 x 建一棵动态开点线段树，下标为 i 的位置维护 x 子树内所有 dis(x,z)=i 的 a_z 的和。

那么求 z 子树内到 z 的距离 \leq k-dis(x,z) 的点权和就在对应线段树上查个区间和就 ok 了。

那 z 在 x 方向上的儿子 s 的子树怎么办呢？

初学点分树的萌新（例如我）很容易进入一个误区，那就是这东西可以在 s 对应的线段树上查 [0,k-dis(x,z)-1] 的和。但这显然是错的，因为两点在点分树上的距离与两点在原树上的距离没有一丁点联系。到 s 距离 \leq k-dis(x,z)-1，并不意味着到 z 距离 \leq k-dis(x,z)。

那么正解是什么呢？考虑对于每个点再建立一棵动态开点线段树，线段树上下标为 i 的位置维护 x 子树内到 fa_x 距离 =i 的点权和。解决 z 在 x 方向上的儿子 s 的子树的问题只需在点 s 的线段树上查询 [0,k-dis(x,z)] 的和就行了。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
    x=0;char c=getchar();T neg=1;
    while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    x*=neg;
}
const int MAXN=1e5;
const int MAXP=5e6;
const int LOG_N=17;
const int INF=1e9;
int n,qu,a[MAXN+5];
int hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int fa[MAXN+5][LOG_N+2],dep[MAXN+5];
void dfs0(int x,int f){
    fa[x][0]=f;
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];if(y==f) continue;
        dep[y]=dep[x]+1;dfs0(y,x);
    }
}
int getlca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LOG_N;~i;i--) if(dep[x]-(1<<i)>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=LOG_N;~i;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int getdis(int x,int y){return dep[x]+dep[y]-(dep[getlca(x,y)]<<1);}
int siz[MAXN+5],mx[MAXN+5],cent=0;
bool vis[MAXN+5];
void findcent(int x,int f,int tot){
    siz[x]=1;mx[x]=0;
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];if(y==f||vis[y]) continue;
        findcent(y,x,tot);chkmax(mx[x],siz[y]);siz[x]+=siz[y];
    } chkmax(mx[x],tot-siz[x]);
    if(mx[x]<mx[cent]) cent=x;
}
int dfa[MAXN+5];
void divcent(int x,int tot){
//  printf("%d\n",x);
    vis[x]=1;
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];if(vis[y]) continue;
        cent=0;int sz=(siz[y]<siz[x])?siz[x]:(tot-siz[x]);
        findcent(y,x,sz);dfa[cent]=x;divcent(cent,sz);
    }
}
struct segtree{
    int rt[MAXN+5],ncnt=0;
    struct node{int ch[2],val;} s[MAXP+5];
    void modify(int &k,int l,int r,int p,int x){
        if(!k) k=++ncnt;
        if(l==r){s[k].val+=x;return;}
        int mid=(l+r)>>1;
        if(p<=mid) modify(s[k].ch[0],l,mid,p,x);
        else modify(s[k].ch[1],mid+1,r,p,x);
        s[k].val=s[s[k].ch[0]].val+s[s[k].ch[1]].val;
    }
    int query(int k,int l,int r,int ql,int qr){
        if(!k) return 0;
        if(ql<=l&&r<=qr) return s[k].val;
        int mid=(l+r)>>1;
        if(qr<=mid) return query(s[k].ch[0],l,mid,ql,qr);
        else if(ql>mid) return query(s[k].ch[1],mid+1,r,ql,qr);
        else return query(s[k].ch[0],l,mid,ql,mid)+query(s[k].ch[1],mid+1,r,mid+1,qr);
    }
} w1,w2;
void modify(int x,int v){
    int cur=x;
    while(cur){
        w1.modify(w1.rt[cur],0,n-1,getdis(cur,x),v);
        if(dfa[cur]) w2.modify(w2.rt[cur],0,n-1,getdis(dfa[cur],x),v);
        cur=dfa[cur];
    }
}
int query(int x,int k){
    int cur=x,pre=0,ret=0;
    while(cur){
        if(getdis(cur,x)>k){
            pre=cur;cur=dfa[cur];continue;
        }
        ret+=w1.query(w1.rt[cur],0,n-1,0,k-getdis(cur,x));
        if(pre) ret-=w2.query(w2.rt[pre],0,n-1,0,k-getdis(cur,x));
        pre=cur;cur=dfa[cur];
    } return ret;
}
int main(){
    scanf("%d%d",&n,&qu);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);adde(u,v);adde(v,u);}
    dfs0(1,0);for(int i=1;i<=LOG_N;i++) for(int j=1;j<=n;j++)
        fa[j][i]=fa[fa[j][i-1]][i-1];
    mx[0]=INF;cent=0;findcent(1,0,n);divcent(cent,n);
//  for(int i=1;i<=n;i++) printf("%d\n",dfa[i]);
    for(int i=1;i<=n;i++) modify(i,a[i]);
    int preans=0;
    while(qu--){
        int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
        x^=preans;y^=preans;
        if(opt==0){preans=query(x,y);printf("%d\n",preans);}
        else{modify(x,y-a[x]);a[x]=y;}
    }
    return 0;
}