思路：搞了一发链剖

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 88888int n,m,first[N],next[N],v[N],w[N],tot,xx,yy,zz,k;int top[N],size[N],deep[N],son[N],fa[N],weight[N];void add(int x,int y,int z){    w[tot]=z,v[tot]=y;    next[tot]=first[x],first[x]=tot++;}void dfs(int x){    size[x]=1;    for(int i=first[x];~i;i=next[i])        if(v[i]!=fa[x]){            fa[v[i]]=x;            deep[v[i]]=deep[x]+1;            weight[v[i]]=weight[x]+w[i];            dfs(v[i]);            size[x]+=size[v[i]];            if(size[son[x]]