【NOIP2016】天天爱跑步
【NOIP2016】天天爱跑步
©题目大意：给你一棵树，经过每一条边的时间为1.告诉你个人分别从各自的起点到各自的终点，每一个节点有一个时间wi，问你每一个节点在wi这一刻能看到几个人在自己这一个节点。
©题解：
这道题可能会想到的一个暴力解法：LCA。模拟路径，逐个标记。但是这是没有必要的。
对于树上的一个节点i，如果起点在他的子树内，终点不在，那么要在这个点看到这个人的充要条件就是w[i]+deep[i]==deep[s]（深度之差就是时间之差）。
对于树上的一个节点i，如果终点在他的子树内，起点不在，那么要在这个点看到这个人的充要条件就是dis(s,t)-w[i]==deep[t]-deep[i]（t为终点，s为起点）（路径长度-i节点观测的时间，就是剩下的从i到终点的时间，也就是深度差了。）
然后LCA使用倍增来求解。我们把这两种状态分开来统计答案，那么需要使用动态数组，将si加入到si与ti的LCA处。然后按照dfs序，每次统计这课子树有多少个路径的起点，使用一个深度的桶来装这一个深度有多少的起点（已经搜过的点内）。那么来到点i记下last，递归回溯之后再次到达点i，就可以利用桶，以及last与结论（w[i]+deep[i]==deep[s]）来ans[i]+=某一个深度的起点的数量即可。要注意一点，统计完答案之后，要把当前这一个点的动态数组中的点从桶中移走。目的就在于使用结论的条件是“如果起点在他的子树内，终点不在。”，故不能将他算在内，之前“将si加入到si与ti的LCA处。”的目的就在于此。
桶清空一下。
对于终点的状态，我们一样的来考虑即可但是最好移一下项，就是“deep[i]-w[i]==deep[t]-dis(s,t)”我们把深度deep[t]-dis(s,t)加入到que1[t]中，同事加入到que2[lca]中，每搜到一个点，就把这一个点的que1中的深度加入到桶中，统计了答案之后（查询“deep[i]-w[i]”来累计答案），在把这个点que2中的深度减去。
最后如果起点和终点的LCA就是起点或终点本身的话，在上面两种情况中，会被重复统计，最后在将所有的LCA的ans--就行了。利用“w[i]+deep[i]==deep[s]”，也就是if(deep[s]-deep[lca]==w[i])ans[lca]--;
©Attention：天天爱跑步的思想可以运用到很多题目中间，在推式子的时候，将与一个点有关的变量全部移动到等式的一边，就可以使用桶来统计答案了。