题目传送门：

题目大意：

(中文题，简单解答下题意)

存在N个城市和M个百度的子公司，N个城市间有N-1条道路连接（一颗树），每个子公司都有办公室，办公室分布在各个城市，现在提问，两个子公司间的最小距离。

分析：

枚举提问的两个子公司的办公室间的距离，求出最短距离即可：

例如：子公司company1办公室在城市 1 2 3     子公司company2的办公室在城市5 6 ,若求company1，company2的最短距离，即枚举（1，5）、（1，6）、（2，5）、（2，6）、（3，5）、（3，6）的距离,求出最小值即可。

求距离：设求城市a，b的距离,先用倍增求出lca（a,b），然后dis=dis[a]+dis[b]-2*dis[lca(a,b)]得到距离;

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAX=100009;const int M=20;int t,n,m,a,b,val,num,q;int head[MAX],cnt=0;int up[MAX][M];int deep[MAX];int dis[MAX];vector
         
          comp[MAX];struct Edge{                                //存树     int next,to,val;}edge[MAX*2];inline void add(int u,int v,int w){    edge[cnt].to=v;    edge[cnt].val=w;    edge[cnt].next=head[u];    head[u]=cnt++;}void dfs(int u)                                    //dfs遍历求出深度和距离 {    for(int i=head[u];i!=-1;i=edge[i].next)    {        int to=edge[i].to;        if(to==up[u][0])continue;        deep[to]=deep[u]+1;        up[to][0]=u;        dis[to]=dis[u]+edge[i].val;        dfs(to);    }}void init()                                         {    for(int j=1;(1<
          
           <=n;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];}int lca(int a,int b){ if(deep[a]
           
            =0;i--) { if(up[a][i]!=up[b][i]) { a=up[a][i];b=up[b][i]; } } return up[a][0];}int main(){ scanf("%d",&t); while(t--) { memset(head,-1,sizeof(head));cnt=0; //初始化 memset(up,0,sizeof(up)); memset(deep,0,sizeof(deep)); memset(dis,0,sizeof(dis)); for(int i=0;i