题目描述
小 C 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。
这个游戏的地图可以看作一棵包含 n 个结点和 n - 1 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从 1 到 n 的连续正整数。
现在有 m 个玩家，第 i 个玩家的起点为 Si，终点为 Ti。每天打卡任务开始时，所有玩家在第 0 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）
小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 j 的观察员会选择在第 Wj 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 Wj 秒也正好到达了结点 j。小 C 想知道每个观察员会观察到多少人？
注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点 j 作为终点的玩家：若他在第 Wj 秒前到达终点，则在结点 j 的观察员不能观察到该玩家；若他正好在第 Wj 秒到达终点，则在结点 j 的观察员可以观察到这个玩家。
输入描述:
第一行有两个整数 n 和 m。其中 n 代表树的结点数量，同时也是观察员的数量，m 代表玩家的数量。
接下来 n - 1 行每行两个整数 u 和 v，表示结点 u 到结点 v 有一条边。
接下来一行 n 个整数，其中第 i 个整数为 Wi，表示结点 j 出现观察员的时间。
接下来 m 行，每行两个整数 Si 和 Ti，表示一个玩家的起点和终点。
对于所有的数据，保证 1 ≤ Si, Ti ≤ n, 0 ≤ Wj ≤ n。
输出描述:
输出一行 n 个整数，第 j 个整数表示结点 j 的观察员可以观察到多少人。
示例1
6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6
2 0 0 1 1 1
对于 1 号点，W1 = 0，故只有起点为 1 号点的玩家才会被观察到，所以玩家 1 和玩家 2 被观察到，共 2 人被观察到。
对于 2 号点，没有玩家在第 2 秒时在此结点，共 0 人被观察到。
对于 3 号点，没有玩家在第 5 秒时在此结点，共 0 人被观察到。
对于 4 号点，玩家 1 被观察到，共 1 人被观察到。
对于 5 号点，玩家 2 被观察到，共 1 人被观察到。
对于 6 号点，玩家 3 被观察到，共 1 人被观察到。
示例2
5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5
1 2 1 0 1
备注
测试点 1 ~2：n = m = 991，所有人的起点等于自己的终点，即 Si = Ti；
测试点 3 ~ 4：n = m = 992，Wj = 0；
测试点 5：n = m = 993；
测试点 6 ~ 8：n = m = 99994，树退化成一条链，对于 1 ≤ i < n，i 与 i + 1 有边；
测试点 9 ~ 12：n = m = 99995，Si = 1；
测试点 13 ~ 16：n = m = 99996，Ti = 1；
测试点 17~ 19：n = m = 99997；
测试点 20：n = m = 299998。
解答
前置知识：树上差分
刷新了我对树上差分的认知
以往的树上差分，一般处理点或边被覆盖多少次
但我们把思路放开，我们可以处理他被某个值覆盖多少次
可以理解一下上面这句话
我们开一个bucket，来存值，就按照正常树上差分的思想去更新，只不过从返回一个值变成开到一个同一个桶里
如果不能理解，可以多看几遍
那么这道题就很简单了，我们把原来的路分为两条路，一条向上，一条向下
对于向上的路，对点i有贡献的情况为
对于向下的路，对点i有贡献的情况为
上面两个式子可以首推，在我理解了上面的树上差分后，我只用了20min推出式子打完代码AC，但一定要理解上面的内容
实在不懂也可以看代码（说不定就懂了）
#include <cstdio>
int read(); void print(int, char);
const int maxn = 312345;
/*链式前向星存图*/
struct edge{ int v, nxt;
}e[maxn<<1]; int fir[maxn], num(0);
inline void add(int u, int v){
e[++num].v = v; e[num].nxt = fir[u]; fir[u] = num;
e[++num].v = u; e[num].nxt = fir[v]; fir[v] = num;
}
/*树剖求lca*/
int siz[maxn], son[maxn], fa[maxn], top[maxn], h[maxn];
void dfs1(int now){
siz[now] = 1;
for(int itr(fir[now]); itr; itr = e[itr].nxt){
if(siz[e[itr].v]) continue;
fa[e[itr].v] = now; h[e[itr].v] = h[now] + 1;
dfs1(e[itr].v); siz[now] += siz[e[itr].v];
if(!son[now] || siz[son[now]] < siz[e[itr].v]) son[now] = e[itr].v;
}
}
void dfs2(int now, int tp){
top[now] = tp; if(son[now]) dfs2(son[now], tp);
for(int itr(fir[now]); itr; itr = e[itr].nxt){
if(top[e[itr].v]) continue;
dfs2(e[itr].v, e[itr].v);
}
}
inline int lca(int u, int v){
for(; top[u] != top[v]; u = fa[top[u]]) if(h[top[u]] < h[top[v]]) u^=v^=u^=v;
return h[u] < h[v] ? u : v;
}
/*存储树上差分的修改操作*/
struct delta{ int v, posi, nxt;
}d[maxn<<2]; int fir1[maxn], fir2[maxn], ds(0);
inline void add1(int p, int val, int posi){
d[++ds].v = val; d[ds].posi = posi;
d[ds].nxt = fir1[p]; fir1[p] = ds;
}
inline void add2(int p, int val, int posi){
d[++ds].v = val; d[ds].posi = posi;
d[ds].nxt = fir2[p]; fir2[p] = ds;
}
int t[maxn], ans[maxn];
int buc1[maxn << 1], buc2[maxn << 1];
/*获取答案*/
void dfs(int now, int fr){
int b1 = buc1[t[now]+h[now]], b2 = buc2[t[now]-h[now]+maxn];
for(int itr(fir[now]); itr; itr = e[itr].nxt){
if(e[itr].v == fr) continue;
dfs(e[itr].v, now);
}
for(int itr(fir1[now]); itr; itr = d[itr].nxt){
buc1[d[itr].v] += d[itr].posi;
}
for(int itr(fir2[now]); itr; itr = d[itr].nxt){
buc2[d[itr].v + maxn] += d[itr].posi;
}//更新桶内的值
ans[now] += buc1[t[now]+h[now]]+buc2[t[now]-h[now]+maxn]-b1-b2;//统计答案
}
int main(){
int n(read()), q(read());
for(int i(1); i < n; ++i) add(read(), read());
for(int i(1); i <= n; ++i) t[i] = read();
dfs1(1); dfs2(1, 1);
for(int i(1), s, T, l; i <= q; ++i){
s = read(), T = read(), l = lca(s, T);
add1(s, h[s], 1); add1(l, h[s], -1);
add2(T, h[s]-2*h[l], 1); add2(l, h[s]-2*h[l], -1);
if(h[s]==h[l]+t[l]) ++ans[l];//我的差分没有做到lca，所以这里直接统计
}
dfs(1, -1);
for(int i(1); i < n; ++i) print(ans[i], ' ');
print(ans[n], '\n');
return 0;
}
void print(int x){
if(x>=10) print(x/10);
putchar(x%10+48);
}
inline void print(int x, char ch){
if(x == 0) putchar('0');
else print(x);
putchar(ch);
}
inline char Getchar(){
static char s[1024], *A(s), *B(s);
return (A==B)&&(B=(A=s)+fread(s,1,1024,stdin),A==B)?EOF:*A++;
}
#ifndef DEBUG
#define Getchar getchar
#endif
inline int read(){
int x(0); char ch(getchar());
while(ch < '0' || ch > '9') ch = getchar();
do x=x*10+(ch&15), ch = getchar(); while(ch >= '0' && ch <= '9');
return x;
} 
京公网安备 11010502036488号