题解 P3258 【[JLOI2014]松鼠的新家】
主要讲一讲
树上差分
顾名思义，树上差分就是在树上的差分（？？？）
学过树状数组（区间修改）的同学应该了解，差分具有很优秀的性质
已知原数组 a[i],设差分数组 b[i]=a[i]-a[i-1]
那么就有 a[i]=b[1]+b[2]+...+b[n]
修改也很方便，例如对于区间（p,q）同时加上x,相当于 b[p]+=n,b[q+1]-=n
接下来就是把线性的差分移到树上，
同理，已知原数组a[i]表示每个点的点权，
我们设差分数组b[i]=a[i]-sum(a[j])(j为i的每个直接相连的儿子)；
不难发现，叶子节点的b[i]恰好为该点点权a[i],此外，对于任意一个节点K，
a[K]=以K为根节点的子树中所有b[i]之和。
如果我们要对树上的一条链(u,v)的点权进行修改(同时加上x)，只需要：
b[u]+=x;
b[v]+=x;
b[lca(u,v)]-=x;
b[fa[lca(u,v)]]-=x;
注意为了不影响到链外的其他点权，lca（u,v）的父节点需要修改，可以自己推一下。
这是点权的情况，如果是边权，只需要把一个点到父亲的边权赋给自己当作点权，
然后当作点权的情况做就好了，细节需要处理一下。
在本题中，原数组初始都是0，所以我们只需要读入、处理，最后遍历整颗树，递
归求出a[i]就ok了
代码：
#include <bits/stdc++.h>
using namespace std;
int h[300000+5],fa[300000+5][25];
int vis[300000+5],lg[300000+5],dep[300000+5];
int a[300000+5],b[300000+5];//a为糖果数,b为差分数组
int m,n,i,j,x,y,tmp;
struct EDGE{
int from,to,next;
};
EDGE e[600000+5];
void add(int a,int b){
tmp++;
e[tmp].from=a;
e[tmp].to=b;
e[tmp].next=h[a];
h[a]=tmp;
}
void dfs1(int k){
int s=h[k];
while(s!=0){
int t=e[s].to;
if(t!=fa[k][0]){
fa[t][0]=k;
dep[t]=dep[k]+1;
dfs1(t);
}
s=e[s].next;
}
}
int lca(int a,int b){
if(dep[a]<dep[b]){
int t=a;
a=b;
b=t;
}
while(dep[a]!=dep[b]){
int k=lg[dep[a]-dep[b]]-1;
a=fa[a][k];
}
if(a==b) return a;
else{
for(j=lg[dep[a]]-1;j>=0;j--){
if(fa[a][j]!=fa[b][j]){
a=fa[a][j];
b=fa[b][j];
}
}
}
return fa[a][0];
}
void dfs2(int k){
int s=h[k];
while(s!=0){
int t=e[s].to;
if(t!=fa[k][0]){
dfs2(t);
b[k]+=b[t];
}
s=e[s].next;
}
}
int main(){
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&vis[i]);
for(i=1;i<=n-1;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1);
for(j=1;j<=20;j++)
for(i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
for(i=1;i<=n;i++)
lg[i]=lg[i-1]+(1<<lg[i-1]==i);
a[vis[1]]++;
for(i=2;i<=n;i++){
int now=lca(vis[i],vis[i-1]);
b[vis[i]]++;
b[vis[i-1]]++;
b[now]--;
b[fa[now][0]]--;
a[vis[i-1]]--;//链首糖果数直接减1
}
a[vis[n]]--;
dfs2(1);
for(i=1;i<=n;i++)
cout<<a[i]+b[i]<<endl;
return 0;
}明天生日写篇题解开心一下