原题链接：https://www.luogu.com.cn/problem/P1600
题目
小c 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线,完成打卡任务。
这个游戏的地图可以看作一一棵包含 �n 个结点和 �−1n−1 条边的树，每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 11 到 �n 的连续正整数。
现在有 �m 个玩家，第 �i 个玩家的起点为 ��si，终点为 ��ti。每天打卡任务开始时，所有玩家在第 00 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树，所以每个人的路径是唯一的)
小c 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 �j 的观察员会选择在第 ��wj 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 ��wj 秒也正好到达了结点 �j 。小c 想知道每个观察员会观察到多少人?
注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一 段时间后再被观察员观察到。 即对于把结点 �j 作为终点的玩家：若他在第 ��wj 秒前到达终点,则在结点 �j 的观察员不能观察到该玩家；若他正好在第 ��wj 秒到达终点,则在结点 �j 的观察员可以观察到这个玩家。
输入格式
第一行有两个整数 �n 和 �m。其中 �n 代表树的结点数量, 同时也是观察员的数量, �m 代表玩家的数量。
接下来 �−1n−1 行每行两个整数 �u 和 �v，表示结点 �u 到结点 �v 有一条边。
接下来一行 �n 个整数，其中第 �j 个整数为 ��wj , 表示结点 �j 出现观察员的时间。
接下来 �m 行，每行两个整数 ��si，和 ��ti，表示一个玩家的起点和终点。
对于所有的数据，保证 1≤��,��≤�,0≤��≤�1≤si,ti≤n,0≤wj≤n。
输出格式
输出 11 行 �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
输出 #1复制
2 0 0 1 1 1
输入 #2复制
5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5
输出 #2复制
1 2 1 0 1
说明/提示
【样例1说明】
对于 11 号点，��=0wi=0，故只有起点为 11 号点的玩家才会被观察到，所以玩家 11 和玩家 22 被观察到，共有 22 人被观察到。
对于 22 号点，没有玩家在第 22 秒时在此结点，共 00 人被观察到。
对于 33 号点，没有玩家在第 55 秒时在此结点，共 00 人被观察到。
对于 44 号点，玩家 11 被观察到，共 11 人被观察到。
对于 55 号点，玩家 11 被观察到，共 11 人被观察到。
对于 66 号点，玩家 33 被观察到，共 11 人被观察到。
【子任务】
每个测试点的数据规模及特点如下表所示。
提示: 数据范围的个位上的数字可以帮助判断是哪一种数据类型。
【提示】
如果你的程序需要用到较大的栈空间 (这通常意味着需要较深层数的递归), 请务必仔细阅读选手目录下的文本文档 running/stack.txt, 以了解在最终评测时栈空间的限制与在当前工作环境下调整栈空间限制的方法。
在最终评测时，调用栈占用的空间大小不会有单独的限制，但在我们的工作环境中默认会有 1MiB1MiB 的限制。 这可能会引起函数调用层数较多时， 程序发生栈溢出崩溃。
我们可以使用一些方法修改调用栈的大小限制。 例如， 在终端中输入下列命令 ulimit -s 1048576
此命令的意义是，将调用栈的大小限制修改为 1GiB1GiB。
例如，在选手目录建立如下 sample.cpp 或 sample.pas
将上述源代码编译为可执行文件 sample 后，可以在终端中运行如下命令运行该程序
./sample
如果在没有使用命令“ ulimit -s 1048576”的情况下运行该程序， sample 会因为栈溢出而崩溃； 如果使用了上述命令后运行该程序，该程序则不会崩溃。
特别地， 当你打开多个终端时， 它们并不会共享该命令， 你需要分别对它们运行该命令。
请注意， 调用栈占用的空间会计入总空间占用中， 和程序其他部分占用的内存共同受到内存限制。
题解
这是茫茫C++中的pascal，难道pascal终要没落？
好了，讲题
##first
首先我们先将题目简化来看看。当树退化为一条链（节点记作a[0]..a[n]），且玩家只往右走时，我们容易推得u号点上的观察员要观察到v号点开始的玩家，那么显然有v + w[u] = u。
##second
我们很自然地将无根树变为有根树（程序中节点1为根，深度为0）。于是从s->t的路径可以表示为s->lca(s,t)->t。对于s->lca(s,t)，我们对应上一条中的结论，单独考虑s、lca(s,t)所在的那条链，不难发现若在这条链上的点u要观察到这个玩家，就有deep[u] - deep[s] = w[u]（路径长度，即深度差等于w[u]）。可推得deep[u] + w[u] = deep[s]。也就是说，u节点子树上点v能够被观察到的必要条件是deep[u] + w[u] = deep[s]。对于lca(s,t)->t也有类似结论（自己算）。所以我们可以开一个桶（vector，C++党不要喷我），记录deep[s]，然后做完了子树，回到u以后统计deep[u] + w[u]。
##third
依旧对于s->lca。上一条中，我们提到u节点子树上点v能够被观察到的必要条件是deep[u] + w[u] = deep[s]。显然若是再加上lca(s,t)是u或它的祖先，那么就变成了充要条件。为了实现这一点，我们可以在做到s的时候改变vector的同时在lca(s,t)上打一个deep[s]的标记，回到lca(s,t)时删除即可。具体的实现可以用链表。对于lca(s,t)->t同样做法。
##fourth
那么还有一个很严肃的问题。如上统计方法，可能会“跨子树运算”。即s和u满足deep[s] = deep[u] + w[u]且lca(s,t)是u或它的祖先（这里一定是它的祖先），但是不满足s在u为根节点的子树上。这时，我们神奇的差分（好像是这么叫的）就登场了。我们可以发现，dfs时，在进入到u之前一定没做过u子树内的点；在回到u时，一定已经做完了u子树内的点且没有做u子树外的点。然后发现其实u需要统计的数（还是拿s->lca(s,t)举例）只是deep[u] + w[u]，那么我们就可以在进入u的时候记录一下桶的值，出去的时候再剪一剪就好了。
##fifth
两条链的焦点，lca(s,t)，有可能被算到两次。那么如何解决？我看到大部分题解都是最后统计，但是本人懒到懒得推最后的式子，就这么做了：在做s->lca(s,t)时，回到u先删打的标记再统计；做lca(s,t)->t时，回到u先统计再删标记，那么lca(s,t)就只被算到了一次。
##具体实现看程序。
var n,m,i,x,y,max_deep:longint; l1,l2,l3,l4:longint; f1,f2,f3,f4,next2,value,next3,goto3,next4,goto4,s,t :array[0..300010] of longint; next1,goto1:array[0..600010] of longint; vector:array[-300010..600010] of longint; b:array[0..300010,0..20] of longint; ans,lca,deep,w,len:array[0..300010] of longint; procedure add1(x,y:longint);//这只是4个数组模拟链表 begin inc(l1); next1[l1] := f1[x]; f1[x] := l1; goto1[l1] := y; end; procedure add2(x,y:longint); begin inc(l2); next2[l2] := f2[x]; f2[x] := l2; value[l2] := y; end; procedure add3(x,y:longint); begin inc(l3); next3[l3] := f3[x]; f3[x] := l3; goto3[l3] := y; end; procedure add4(x,y:longint); begin inc(l4); next4[l4] := f4[x]; f4[x] := l4; goto4[l4] := y; end; procedure load_lca(u,fa,depth:longint);//建树，顺便初始化一下树上倍增求lca（可以用Tarjan） var x,i:longint; begin if depth > max_deep then max_deep := depth; deep[u] := depth; b[u][0] := fa; for i := 1 to 19 do b[u][i] := b[b[u][i - 1]][i - 1]; x := f1[u]; while x <> 0 do begin if goto1[x] <> fa then load_lca(goto1[x],u,depth + 1); x := next1[x]; end; end; procedure dfs1(u,fa:longint);//s->lca var x,t:longint; begin if deep[u] + w[u] <= max_deep then t := vector[deep[u] + w[u]]; x := f1[u]; while x <> 0 do begin if goto1[x] <> fa then dfs1(goto1[x],u); x := next1[x]; end; x := f3[u]; while x <> 0 do//改桶，在lca上打标记 begin inc(vector[deep[u]]); add2(lca[goto3[x]],deep[u]); x := next3[x]; end; x := f2[u]; while x <> 0 do//删标记 begin dec(vector[value[x]]); x := next2[x]; end; if deep[u] + w[u] <= max_deep then//统计 inc(ans[u],vector[deep[u] + w[u]] - t); end; procedure dfs2(u,fa:longint); var x,t:longint; begin t := vector[deep[u] - w[u]]; x := f1[u]; while x <> 0 do begin if goto1[x] <> fa then dfs2(goto1[x],u); x := next1[x]; end; x := f4[u]; while x <> 0 do begin inc(vector[deep[u] - len[goto4[x]]]); add2(lca[goto4[x]],deep[u] - len[goto4[x]]); x := next4[x]; end; inc(ans[u],vector[deep[u] - w[u]] - t); x := f2[u]; while x <> 0 do begin dec(vector[value[x]]); x := next2[x]; end; end; function get_lca(x,y:longint):longint;//返回lca(x,y) var t,i:longint; begin if deep[x] < deep[y] then begin t := x; x := y; y := t; end; t := deep[x] - deep[y]; for i := 0 to 19 do if ((t >> i) and 1) = 1 then x := b[x][i]; if x = y then exit(x); for i := 19 downto 0 do if b[x][i] <> b[y][i] then begin x := b[x][i]; y := b[y][i]; end; exit(b[x][0]); end; begin read(n,m); for i := 1 to n - 1 do begin read(x,y); add1(x,y); add1(y,x); end; load_lca(1,1,0); for i := 1 to n do read(w[i]); for i := 1 to m do begin read(s[i],t[i]); lca[i] := get_lca(s[i],t[i]); add3(s[i],i); add4(t[i],i);//这样可以快速地找到那些玩家在某个点开始/结束 len[i] := deep[s[i]] + deep[t[i]] - 2 * deep[lca[i]]; end; dfs1(1,1); fillchar(f2,sizeof(f2),0); l2 := 0; fillchar(next2,sizeof(next2),0); fillchar(vector,sizeof(vector),0); fillchar(value,sizeof(value),0); dfs2(1,1); for i := 1 to n do write(ans[i],' '); end.
