NOIP2016 Day1 天天爱跑步 题解

第一次出题好激动啊,这题是我在军训时候开脑洞想起来出的,其实一开始题目比这个难,但是我发现我做不出来了。最后经过多次迭代题目变成了这个样子。这个解法是某次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不是原题的$T_i$),在扫描到$pre_{T_i}$时, 给$a[deep[S_i]]$加上1;扫描到$suf_{T_i}$时,给$a[deep[S_i]]$减去1。
    类似的,对于向下的路径,有$W_j - deep[j] = total_len - deep[T_i]$,其中$total_len$为路径的长度。之后可以用类似的算法做出来。

 

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

ymy

还有天天小朋友长这样:

tt

以及我阿甘快刷不完了

冬天的圆明园还不错