题目描述：

有一棵N个节点的树, 令d(i,j)为i到j经过的边的条数。有M个炸弹, 第i个炸弹在节点posi上, 威力为power i,它会对所有节点j造成max(0,power i−d(posi,j))的伤害。

求出每个节点最终受到的伤害。

算法标签：点分治

思路：

考虑对于每次求点，仅求以当前重心为根时，不同子树之间的贡献。每次处理出炸弹到根的距离和每个点到根距离，我们会发现对于在同一个子树的答案我们会多算，所以再对每个子树单独做一次，减去多算的答案。

以下代码：

#include
      
       #define il inline#define LL long long#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=2e5+5,M=5e5+5;int sz[N],d[N],son[N],rt,size,md,A[N],tt,num[N];bool vis[N];int n,m,head[N],ne[N<<1],to[N<<1],cnt,hd[N],val[M],nx[M],tot;LL res[N],sum[N];il int read(){
    int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;}il void insert(int x,int y){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}il void ins(int x,int y){nx[++tot]=hd[x];hd[x]=tot;val[tot]=y;}il void getrt(int x,int fa){    son[x]=sz[x]=1;    for(int i=head[x];i;i=ne[i]){        if(fa==to[i]||vis[x])continue;        getrt(to[i],x);sz[x]+=sz[to[i]];        son[x]=max(son[x],sz[to[i]]);    }    son[x]=max(son[x],size-sz[x]);    if(son[x]
       
        md)md=d[x];A[++tt]=x;    for(int i=head[x];i;i=ne[i]){        if(fa==to[i]||vis[to[i]])continue;        d[to[i]]=d[x]+1;getmd(to[i],x);    }}il void dfs(int x,int fa){    for(int i=hd[x];i;i=nx[i]){        int v=min(val[i]-d[x],md);        if(v>0)sum[v]+=val[i]-d[x],num[v]++;    }    for(int i=head[x];i;i=ne[i]){        if(fa==to[i]||vis[to[i]])continue;        dfs(to[i],x);    }}il void work(int x,int dep,int f){    tt=md=0;d[x]=dep;getmd(x,0);md++;    for(int i=0;i<=md;i++)sum[i]=0,num[i]=0;    dfs(x,0);    for(int i=1;i<=md;i++)sum[i]+=sum[i-1],num[i]+=num[i-1];    for(int i=1;i<=tt;i++){        int u=A[i];        res[u]+=1ll*(sum[md]-sum[d[u]]-1ll*d[u]*(num[md]-num[d[u]]))*f;    }}il void solve(int x){    vis[x]=1;work(x,0,1);    for(int i=head[x];i;i=ne[i]){        if(vis[to[i]])continue;        work(to[i],1,-1);    }    for(int i=head[x];i;i=ne[i]){        if(vis[to[i]])continue;        rt=0;getrt(to[i],x);solve(rt);    }}int main(){    n=read();m=read();    for(int i=2;i<=n;i++){
    int x=read();insert(i,x);insert(x,i);}    for(int i=1;i<=m;i++){
    int x=read(),y=read();ins(x,y);}    size=n;son[0]=n;getrt(1,0);solve(rt);    for(int i=1;i<=n;i++)printf("%lld\n",res[i]);    return 0;}