记录编号	303295	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	GROWL GOOD BOYส็	是否通过	通过
代码语言	C++	运行时间	0.297 s
提交时间	2016-09-05 10:05:53	内存使用	1.62 MiB

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector> 
 
using namespace std;
 
const int maxn=20000+100;
 
int fa[maxn];
 
int dist[maxn],colr[maxn];
 
 
int Ans[maxn*2];
 
vector<int> Ask[maxn];
vector<int> g[maxn];
vector<int> ord[maxn];
vector<int> dis[maxn];
 
int N,M;
 
int Find(int x)
{
    int fx=x,zh;
    while(fa[fx]!=fx)
    {fx=fa[fx];}
    while(fa[x]!=fx)
    {
     zh=fa[x],fa[x]=fx,x=zh;
    }
    return fx;
}
 
void DFS(int x)
{
     colr[x]=1;fa[x]=x;
     int len=g[x].size();
     for(int t,d,i=0;i<len;i++)
     {
             t=g[x][i];
             d=dis[x][i];
             if(!colr[t])
             {
                 //vis[t]=1;
                 dist[t]=dist[x]+d;
                 DFS(t); 
                 fa[t]=x;
             }
     }
     int len1=Ask[x].size();
     for(int t,pos,i=0;i<len1;i++)
     {
             t=Ask[x][i];pos=ord[x][i];
             if(colr[t]==-1)
             {
               Ans[pos]=dist[x]+dist[t]-2*dist[Find(t)];
             }
     }
     colr[x]=-1;
}
int main()
{
    freopen("distance.in","r",stdin);
    freopen("distance.out","w",stdout);
    scanf("%d%d",&N,&M);
    //for(int i=1;i<=N;i++)fa[i]=i;
    for(int x,y,z,i=1;i<N;i++)
    {
    scanf("%d%d%d",&x,&y,&z);
    g[x].push_back(y);
    g[y].push_back(x);
    dis[x].push_back(z);
    dis[y].push_back(z);
    }
    for(int s,t,i=1;i<=M;i++)
    {
            scanf("%d%d",&s,&t);
            Ask[s].push_back(t);
            ord[s].push_back(i);
            Ask[t].push_back(s);
            ord[t].push_back(i);
    }
    dist[1]=0;
    DFS(1);
    for(int i=1;i<=M;i++)printf("%d\n",Ans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}