NOIP 2016系列解题报告 – [题组/NOIP]

Day1 T2 天天爱跑步

你可以点击这个链接下载全部的AC代码
题目传送门(LOJ)

题解 :

​ 跪烂,T1那么水T2直接这么难真的好么,NOIP2016最难的题没有之一。


上面都是扯淡

​ 这题有一个在数据范围上做的很强的提示 : 有一部分数据的起点/终点只从1开始。

我们可以把每个询问拆成两半 S_i \rightarrow LCA(S, T), LCA(S,T)\rightarrow T_i

如果观察员 i 想要看到前一半,那么 dep[S]-dep[i] = w[i] \rightarrow dep[i]+w[i] = dep[S] \;\;(1)

如果观察员 i 想要看到后一半, 那么 len-(dep[T]-dep[i]) = w[i] \rightarrow w[i]-dep[i] = len-dep[T]\;\;(2)

i 要是 T 的祖先

iLCA 的子树中。

​ 我们可以用桶记录上面说的两个值,如果不考虑 iLCA 的子树中,只要当 DFS 到 i 的时候做一个差分,先记录之前有多少点的 (1), (2) 值符合当前点的要求,记为 S_1 当退出 i 的时候先加入 i 点的玩家,再同样查询这样的值记为 S_2 S_2-S_1 就是这个点对应的答案。

​ 但是要考虑在子树中的情况,我们就得加一些操作,只需要在 LCA 和它父亲中加入 dep[S]len-dep[T] ,权值都是 -1 即可

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注