题意：王国有N个城市(1~N)，首都在1。已知有M条路，其中N-1条路构成一棵树T，保证从首都到所有节点的最短路都在这棵树上。现在要求每个节点在当树T上从1到该节点的路径的最后一条边坏掉的情况下的从1到它的最短路。
LCA。对于每个节点v，题目所求的最短路或者是在它的子树T'外的点连一条边到它，或者是在它的子树T'外的点连一条边到T‘中任意一点，延最初的最短路走到该点。这样，对于每个节点，处理每条与其相连的不在树T上的边。设边上另一点为u，则按照LCA(u,v)=i不同值建立不同的集合Ti。然后按照从1到v的路径的顺序来，每次在当前可使用的边选出最小值加上沿树T往上走到节点i的值去更新对于i的答案，同时把Ti中所有边置为可使用。