图论进阶
P1600 「NOIP2016TG」天天爱跑步
将每个玩家的路径拆成两段，分别是起点到 LCA 和 LCA 到终点，所以所有路径都变成了直链，而出发时间不一定为 \(0\) 了。
先考虑从上往下走的路径，简单移项可以得到若玩家能被某个观察员观察到当且仅当玩家出发时间减去起点深度等于观察员观察时间减去观察员深度。只与自身有关，用桶记录玩家，在遇到观察员的时候统计即可。
再来考虑从下往上的路径，简单移项可以得到若玩家能被某个观察员观察到当且仅当玩家出发时间加上起点深度等于观察员观察时间加上观察员深度。只与自身有关，用桶记录玩家，在离开观察员的时候统计即可。
P2680 「NOIP2015TG」运输计划
看见最大的最小果断考虑二分答案。
对于超时的每一条路径，我们必须修改其上面的某一条边，利用树上差分可以找出哪些边是经过了超时的每一条路径的。
将花费时间最长的边改造成虫洞显然最优，这样就能完成 check 了。
P3398 仓鼠找 sugar
很经典的问题，判断树上两条路径是否有交点。
如果某个 LCA 在另一条路径上则说明有交点，否则没有。
证明分类讨论下即可，不难。
P4408 「NOI2003」逃学的小孩
结论很一眼，最优解 \(A,B\) 一定可以位于某条直径的两个端点，然后暴力枚举 \(C\) 计算即可，下面来证明。
首先如果存在多条直径，为了第一段路径尽可能长显然 \(C\) 一定也位于某条直径的端点，根据对称性我们只需要考虑任意一条直径的情况即可。
设 \(AC,BC,AB\) 三段路径交点为 \(D\)，简单画下图可以发现若 \(CD\) 不是最短，更换 \(A,B,C\) 使得 \(CD\) 最短一定不劣。
令 \(D\) 为整棵树的根，那么 \(A,B,C\) 必然是根分开的最深的三棵子树中最深的三个点。根据直径的结论 \(A,B\) 中必然有一个点为某个直径的端点。
若 \(AB\) 不为直径也就是说 \(A\) 所在子树中某个点与 \(A\) 形成了直径或是 \(B\) 所在子树中某个点与 \(B\) 形成了直径，那么将另一个换过来显然更优。
当然 \(C\) 可能也要换，不过这不重要了，反正是暴力枚举的。
P1351 「NOIP2014TG」联合权值
距离为 \(2\) 无非两种情况，爷爷和孙子或者互为兄弟，枚举父亲，前者找儿子中的最大值，后者找儿子中的最大值和次大值。
P5836 「USACO19DEC」Milk Visits S
将同种奶牛缩成一个点，可以发现仍然是一棵树。只有起点和终点位于同一个连通块并且不是朋友喜欢的种类时朋友才会不高兴。