题干：
《天天爱跑步》游戏的地图可以看作一棵包含 n 个结点和 n?1 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从 1 到 n 的连续正整数。现在有 m 个玩家，第 i 个玩家的起点为 Si ，终点为 Ti。每天打卡任务开始时，所有玩家在第 0 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 j 的观察员会选择在第 W?j 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 Wj 秒也正好到达了结点 j。小 C 想知道每个观察员会观察到多少人？
注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点 j 作为终点的玩家：若他在第 Wj 秒前到达终点，则在结点 j 的观察员不能观察到该玩家；若他正好在第 W?j 秒到达终点，则在结点 j 的观察员可以观察到这个玩家。
题解：
每个玩家的跑步路线可视为树上的一条链，可以拆成两段，一段从 s 到 lca(s,t) ，另一段从 lca(s,t) 到 t。其实，要想侦查员可以看到玩家，也就只有两种情况：
1、当侦查员出现在 s～lca(s,t) 之间的 x 节点处时，只有满足玩家从s跑到x的时间d【s】-d【x】等于观察员出现的时间w【x】时才可以。（即d【s】-d【x】=w【x】）
2、当侦查员出现在 lca(s,t)～t 之间的 x 节点处时，只有满足玩家从s跑到x的时间d【s】+d【x】-2d【lca(s,t)】 等于观察员出现的时间w【x】时才可以。（即d【s】+d【x】-2d【lca(s,t)】=w【x】）。
又因为两个条件都包含对 x 所在路径的限制却互不重叠影响，可以分开求每个满足条件的玩家再相加。
我们将关于i的变量放在一侧，关于x的变量放在另一侧，就有：
d【s】=d【x】+w【x】 d【s】-2d【lca(s,t)】=w【x】-d【x】
也就是说，本题可转化为：
有m个玩家，每个玩家i给si～lca(si,ti) 的路径上的每个点加一个价值为 d【si】 的物品，
求在每个点 x 处价值为 d【x】+w【x】 的物品的数量
（第一个情况）
有m个玩家，每个玩家i给lca(si,ti)～ti 的路径上的每个点加一个价值为 d【si】-2d【lca(si,ti)】 的物品，
求在每个点 x 处价值为w【x】-d【x】 的物品的数量
（第二个情况）
树上的区间加？那就用树上差分就可以了，用动态开点的权值线段树来维护。
注意权值线段树的左右范围应是 -n-5～n+5 ，要留有余地，毕竟有 d【si】-2d【lca(si,ti)】 这种极有可//代码效果参考：http://www.jhylw.com.cn/202424651.html
能是负数的物品。像作者就没有开几个数组来存哪几个数出现了几次，而是将其分为两种情况，分别来维护。
Code：
1 #include
2 #include
3 #include
4 #define $ 300000
5 #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:S++)
6 using namespace std;
7 const int L=1[20|1;
8 char buffer【L】,S,T;
9 inline int read(){
10 char a=getchar();
11 int sum=0;
12 while(a[span style="color: rgba(128, 0, 0, 1)">'0'||a>'9') a=getchar();
13 while(a>='0'&&a<='9') sum=(sum[1)+(sum[3)+a-'0',a=getchar();
14 return sum;
15 }
16 inline void swap(int &x,int &y){ int t=y; y=x; x=t; }
17 int m,n,w【$】,first【$】,tot,l【$】,r【$】,ls【$】,rs【$】,dep【$】,dad【$】【22】,shu,sum【$】,self【$】;
18 int ans【$】,root【$】,add;
19 struct node{ int to,next; }a【$2】;
20 struct trie{ int ls,rs,sum1,sum2; }//代码效果参考：http://www.jhylw.com.cn/520741727.html
tree【$20】;21 inline void aadd(int x,int y){
22 a【++tot】=(node){ y,first【x】 };
23 first【x】=tot;
24 a【++tot】=(node){ x,first【y】 };
25 first【y】=tot;
26 }
27 inline void pushup(int x){
28 int l=tree【x】.ls,r=tree【x】.rs;
29 tree【x】.sum1=tree【l】.sum1+tree【r】.sum1;
30 tree【x】.sum2=tree【l】.sum2+tree【r】.sum2;
31 }
32 inline void insert(int &x,int opt,int l,int r,int val,int derta){
33 if(!x) x=++shu;
34 if(l==r){
35 if(!opt) tree【x】.sum1+=derta;
36 else tree【x】.sum2+=derta;
37 return;
38 }
39 int mid=(l+r)]1;
40 if(val<=mid) insert(tree【x】.ls,opt,l,mid,val,derta);
41 else insert(tree【x】.rs,opt,mid+1,r,val,derta);
42 pushup(x);
43 }
44 inline int merge(int x,int y,int l,int r){
45 if(!x||!y) return x+y;
46 if(l==r){
47 tree【x】.sum1+=tree【y】.sum1;
48 tree【x】.sum2+=tree【y】.sum2;
49 return x;
50 }
51 int mid=(l+r)]1;
52 tree【x】.ls=merge(tree【x】.ls,tree【y】.ls,l,mid);
53 tree【x】.rs=merge(tree【x】.rs,tree【y】.rs,mid+1,r);
54 pushup(x);
55 return x;
56 }
57 inline int query(int x,int opt,int l,int r,int val){
58 if(l==r){
59 if(!opt) return tree【x】.sum1;
60 else return tree【x】.sum2;
61 }
62 int mid=(l+r)]1;
63 if(val<=mid) return query(tree【x】.ls,opt,l,mid,val);
64 else return query(tree【x】.rs,opt,mid+1,r,val);
65 }
66 inline void bfs(){
67 queue[span style="color: rgba(0, 0, 255, 1)">int
68 q.push(1); dep【1】=1;
69 while(q.size()){
70 int x=q.front(); q.pop();
71 for(register int i=first【x】;i;i=a【i】.next){
72 int to=a【i】.to;
73 if(dep【to】) continue;
74 dep【to】=dep【x】+1;
75 dad【to】【0】=x;
76 for(register int j=1;j<=20;++j) dad【to】【j】=dad【dad【to】【j-1】】【j-1】;
77 q.push(to);
78 }
79 }
80 }
81 inline void dfs(int x){
82 for(register int i=first【x】;i;i=a【i】.next){
83 int to=a【i】.to;
84 if(to==dad【x】【0】) continue;
85 dfs(to);
86 root【x】=merge(root【x】,root【to】,-add,add);
87 }
88 ans【x】=query(root【x】,0,-add,add,w【x】+dep【x】)
89 +query(root【x】,1,-add,add,w【x】-dep【x】);
90 }
91 inline int LCA(int x,int y){
92 if(dep【x】[span style="color: rgba(0, 0, 0, 1)">dep【y】) swap(x,y);
93 for(register int i=20;i>=0;--i)
94 if(dep【dad【x】【i】】>=dep【y】) x=dad【x】【i】;
95 if(x==y) return x;
96 for(register int i=20;i>=0;--i)
97 if(dad【x】【i】!=dad【y】【i】) x=dad【x】【i】, y=dad【y】【i】;
98 return dad【x】【0】;
99 }
100 signed main(){
101 scanf("%d%d",&n,&m); add=n+5;
102 for(register int i=1,x,y;i
103 for(register int i=1;i<=n;++i) scanf("%d",&w【i】); bfs();
104 for(register int i=1,x,y,lca;i<=m;++i){
105 scanf("%d%d",&x,&y);
106 lca=LCA(x,y);
107 insert(root【x】,0,-add,add,dep【x】,1);
108 insert(root【dad【lca】【0】】,0,-add,add,dep【x】,-1);
109 insert(root【y】,1,-add,add,dep【x】-2dep【lca】,1);
110 insert(root【lca】,1,-add,add,dep【x】-2dep【lca】,-1);
111 }
112 dfs(1);
113 for(register int i=1;i<=n;++i) printf("%d ",ans【i】);
114 }
View Code
附《雨天的尾巴》Code：（数组版）
1 #include
2 #include
3 #include
4 #include
5 #include
6 #define $ 5000010
7 using namespace std;
8 int sum【$】,self【$】,ls【$】,rs【$】,root【$】,dad【$】【30】,dadsiz,tot,first【$】,siz;
9 int dep【$】,ans【$】,m,n,gai【$】;
10 struct tree{ int to,next; }a【$*2】;
11 struct query{ int x,y,z; }qu【$】;
12 inline void swap(int &x,int &y){ int t=x; x=y; y=t; }
13 inline void add(int x,int y){
14 a【++tot】.to=y;
15 a【tot】.next=first【x】;
16 first【x】=tot;
17 a【++tot】.to=x;
18 a【tot】.next=first【y】;
19 first【y】=tot;
20 }
21 inline void bfs(int x){
22 queue[span style="color: rgba(0, 0, 255, 1)">int
23 q.push(x); dep【x】=1;
24 while(q.size()){
25 int xx=q.front(); q.pop();
26 for(register int i=first【xx】;i;i=a【i】.next){
27 int to=a【i】.to;
28 if(dep【to】) continue;
29 dep【to】=dep【xx】+1;
30 dad【to】【0】=xx;
<span style="color: r
