树上倍增

题目链接题意有一棵树A 在点 1，B 在点 2A的移动速度是每秒走过一条边，B的移动速度是每秒走过两条边（也可以只走一条）前 t 秒 A 在不断的走向 B，B 不动之后 B 开始移动，开始追 A，A 开始逃离求问 A 最晚被追到的时间分析首先 A 在 t 秒的时候所在的位置是固定的，因为树上任意两点间路径是唯一的。所以可以把 B 为根，用树上倍增的方式来快速找到 A 的第 t 个祖先，即 A 开始的位置。接下来 A 和 B 会开始追击，考虑到达每一个点的情况，考虑 A 到达每个点所需要的

题目链接：点击查看题目大意：去原网址看吧题目分析：因为是在刷克鲁斯卡尔重构树的题目，所以稍微思考一下就能想出解法了，首先如果水位线固定了，剩下的边组成的最小生成树也是一定的，此时同一个连通块内的点对答案的贡献都是相同的，因为车子可以随便开，这样连通块的贡献，就是连通块内距离点 1 最近的点了这样如何找相应的连通块呢？可以对所有边降序排序，建立克鲁斯卡尔重构树，对于点 x 来说，找到权值大于水位线，且深度最小的祖先，这一步可以用树上倍增来完成，此时这个祖先的子树中的点两两都可以互相达到了，显然包括