P1600 [NOIP2016 提高组] 天天爱跑步 （树上差分）

对于一条路径，s-t，位于该路径上的观察员能观察到运动员当且仅当以下两种情况成立：(d[ ]表示节点深度)

1.观察员x在s-lca(s,t)上时，满足d[s]=d[x]+w[x]就能观察到，所以我们在这条路径上每个点都放置一个d[s]的物品（差分实现），所有路径处理完后dfs一遍，查询每个节点d[x]+w[x]的物品有多少个就是该种情况的答案。

2.观察员x在lca(s,t)-t上时，同理有d[s]+d[t]-2*d[z]-w[x]=d[t]-d[x]，移项的d[s]-2*d[z]=w[x]-d[x]，放置d[s]-2*d[z]的物品，查询w[x]-d[x]的物品有多少个，（注意w[x]-d[x]有可能是负数，所以都加上一个n）。

代码中用vector存每个节点的物品，a1，a2是第一种情况的+1和-1；b1，b2是第二种情况的+1和-1；

对于查询子树和，开两个桶实现（全局开桶），满足区间减法，递归回溯回来后-刚遍历时就是子树和，也就是答案。

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<algorithm>

 5 #include<cmath>

 6 #include<vector>

 7 #include<queue>

 8 using namespace std;

 9 const int N=300010;

10 int to[N<<1],nxt[N<<1],head[N],tot;

11 int f[N][20],d[N],w[N],v[N];

12 int c1[N<<1],c2[N<<1],ans[N];

13 int n,m,t;

14 queue<int> q;

15 vector<int> a1[N],b1[N],a2[N],b2[N];

16

17 void add(int x,int y){

18     nxt[++tot]=head[x];

19     head[x]=tot;

20     to[tot]=y;

21 }

22

23 void bfs(){

24     t=log(n)/log(2);

25     q.push(1);d[1]=1;

26     while(q.size()){

27         int x=q.front();q.pop();

28         for(int i=head[x];i;i=nxt[i]){

29             int y=to[i];

30             if(d[y]) continue;

31             d[y]=d[x]+1;

32             f[y][0]=x;

33             for(int j=1;j<=t;j++)

34                 f[y][j]=f[f[y][j-1]][j-1];

35             q.push(y);

36         }

37     }

38 }

39

40 int lca(int x,int y){

41     if(d[x]>d[y]) swap(x,y);

42     for(int i=t;i>=0;i--)

43         if(d[f[y][i]]>=d[x]) y=f[y][i];

44     if(x==y) return x;

45     for(int i=t;i>=0;i--)

46         if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

47     return f[x][0];

48 }

49

50 void dfs(int x){

51     int val1=c1[d[x]+w[x]],val2=c2[w[x]-d[x]+n];//防止负数，加一个n

52     v[x]=1;

53     for(int i=head[x];i;i=nxt[i]){

54         int y=to[i];

55         if(v[y]) continue;

56         dfs(y);

57     }

58     for(int i=0;i<a1[x].size();i++) c1[a1[x][i]]++;

59     for(int i=0;i<b1[x].size();i++) c1[b1[x][i]]--;

60     for(int i=0;i<a2[x].size();i++) c2[a2[x][i]+n]++;

61     for(int i=0;i<b2[x].size();i++) c2[b2[x][i]+n]--;

62     ans[x]+=c1[d[x]+w[x]]-val1+c2[w[x]-d[x]+n]-val2;//末态-初态，相当于就是统计了子树和

63 }

64

65 int main(){

66     cin>>n>>m;

67     for(int i=1;i<n;i++){

68         int x,y;

69         scanf("%d%d",&x,&y);

70         add(x,y);add(y,x);

71     }

72     for(int i=1;i<=n;i++) scanf("%d",&w[i]);

73     bfs();

74     for(int i=1;i<=m;i++){

75         int x,y;scanf("%d%d",&x,&y);

76         int z=lca(x,y);

77         a1[x].push_back(d[x]);

78         b1[f[z][0]].push_back(d[x]);

79         a2[y].push_back(d[x]-2*d[z]);

80         b2[z].push_back(d[x]-2*d[z]);

81     }

82     dfs(1);

83     for(int i=1;i<n;i++) printf("%d ",ans[i]);

84     printf("%d\n",ans[n]);

85     return 0;

86 }

P1600 [NOIP2016 提高组] 天天爱跑步 （树上差分）的相关教程结束。