正题

题目大意

n个点的一棵树，增加了m条密道。对于树上每条边 $(A, B)$ 被破坏后，要求 $A\sim B$ 经过密道最短。

解题思路

引理:对于每个道路被破坏，最多只会经过一条边。

证明:对于每个答案，被破坏后，所在层数低的点找到一条可以走出他的子树的边就好了，如果要走两条边，中间的点要不在子树中，要不在子树外。在子树中直接那个点走就好了，在子树外就不用再走了。

证毕

所以我们就只需要找那一条密道就好了，我们考虑用并查集，先将密道长度排好，然后在每一条密道

(x, y, w)

，就看一下

x

和

y

之前有没有合并，如果有，就直接用那个答案，如果没有，就合并，用新的答案。

code

#include
   
    #include
    
     #include
     
      #define N 100010using namespace std;struct node{
   	int to,id,next;}a[N*2];struct line{
   	int x,y,w;}e[N];int ls[N],tot,x,y,w,ans,dep[N],father[N];int n,m,S,dfn[N],end[N],cnt,p[N],f[N],d[N];void addl(int x,int y,int w)//加边{
   	a[++tot].to=y;a[tot].id=w;	a[tot].next=ls[x];ls[x]=tot;}bool cmp(line x,line y){
   return x.w
      
       dep[v]?u:v,e[i].w);//将所有的点都get	}	for(int i=1;i