思路：这题我是看 漆子超《分治算法在树的路径问题中的应用》写的。

附代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define Maxn 10010#define Maxm 20010#define inf 0x7fffffffusing namespace std;int head[Maxn],vi[Maxn],e,ans,num,k,n;int mx[Maxn],mi,dis[Maxn],root,size[Maxn];struct Edge{    int u,v,val,next;}edge[Maxm];void init(){    memset(vi,0,sizeof(vi));    memset(head,-1,sizeof(head));    memset(mx,0,sizeof(mx));    memset(dis,0,sizeof(dis));    e=ans=0;}void add(int u,int v,int val){    edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++;    edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++;}void dfssize(int u,int fa){    int i,v;    size[u]=1;    mx[u]=0;    for(i=head[u];i!=-1;i=edge[i].next)    {        v=edge[i].v;        if(v!=fa&&!vi[v])        {            dfssize(v,u);            size[u]+=size[v];            if(size[v]>mx[u]) mx[u]=size[v];        }    }}void dfsroot(int r,int u,int fa){    int v,i;    if(size[r]-size[u]>mx[u]) mx[u]=size[r]-size[u];    if(mx[u]
          
           k&&i