Little Sub and AA

http://acm.hznu.edu.cn/OJ/problem.php?cid=1263&pid=11

http://acm.hznu.edu.cn/OJ/problem.php?id=2590

题意：从S到T，可以随着环境变化随时改变线路，有个人会在某个时候按下按钮使得和你相邻的某条边不能走，这样的事情只会发生一次。问最优策略下最坏情况的最短路径。

C++版本一

题解：

  先处理一个子问题：对于任何一条边，去掉该边后端点i到T的最短路径f[i]。

  从T跑出一棵最短路树，因为如果边不在最短路树上，那么依然是最短路长度，否则的话，考虑将树上y到fa[y]该边去掉，则是在子树中取一个点，跳横跳边再往上到根，也就是dist[x]-dist[y]+edge[x,p]+dist[p]。

C++版本二

我们可以先对于每个点求出最小的dist[x]+edge[x,p]+dist[p]，考虑非树边(x,p)，若x在z的子树内，p不在z的子树内，则该值就可以对z的f产生贡献。我们枚举每一条非树边，对于(x,y)，则将x到lca(x,y)之下的每个点都更新掉，用树链剖分实现。然后把所有的f[i]都减去dist[i]就得到真正的f[i]。 

  得到f之后，从T向S跑最短路，但是更新答案的时候要用  max(d[x]+edge[p].w,f[edge[p].adj])来更新答案。

  意义为如果走最短路比我按按钮结束游戏要劣，那我就等着。

C++版本三

  二分答案也是另一个求解方法。