第一次出题好激动啊，这题是我在军训时候开脑洞想起来出的，其实一开始题目比这个难，但是我发现我做不出来了。最后经过多次迭代题目变成了这个样子。这个解法是某次ddl干不完于是去厕所冷静一发想出来的。

首先是求出来每条路径的LCA，倍增或者Tarjan都行。接下来路径变成向下和向上的路径。

先考虑向上的路径。对于节点$j$的$W_j$，只有起点距离$j$为$W_j$的路径可以被观察到。所以对于起点$S_i$，只有$deep[S_i] = deep[j] + W_j$的时候才能被$j$观察到，这样对于每个询问问题就成了：子树中有多少路径起点的深度值为$deep[j] + W_j$，且这个路径经过自己。这是个经典的离线问题，首先可以DFS一遍求出DFS序，之后一颗子树在序列上是连续的，所以相当于问一个区间有多少值为$deep[j] + W_j$,从左往右扫描一遍即可。记$pre_i$为DFS时初次访问节点$i$的dfs序，$suf_i$为退出节点$i$时的dfs序，再记录一个数组$a$，那么离线起来有这些事件：

• 对于一个$W_j$，在扫描到$pre_j$时候记录下$a[deep[j] + W_j]$的值；扫描到$suf_j$的时候再记录下$a[deep[j]+W_j]$的值，两次做差就是$j$观察到人数
• 对于一个向上的路径，起点为$S_i$，终点为$T_i$（这里的$T_i$是LCA不是原题的$Ti$），在扫描到$pre{T_i}$时， 给$a[deep[Si]]$加上1；扫描到$suf{T_i}$时，给$a[deep[S_i]]$减去1。 类似的，对于向下的路径，有$W_j - deep[j] = total_len - deep[T_i]$，其中$total_len$为路径的长度。之后可以用类似的算法做出来。

比赛的时候有个小插曲，当时我们班组织在圆明园玩，突然微信群上看到说我题目样例描述有问题…

还有天天小朋友长这样：

以及我阿甘快刷不完了

冬天的圆明园还不错