记录编号	536528	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.178 s
提交时间	2019-07-08 09:44:44	内存使用	15.53 MiB

      #include<bits/stdc++.h>
        using namespace std;
        struct qwq{
        	int to,v,next; 
        }a[40005];
        struct  wqw{
        	int num,to,next,flag;
        }que[40005];
        int ans[40005],tot1,tot2,head1[40005],head2[40005];
        int f[40005],len[40005]={0};
        bool vis[40005];
        void add(int x,int y,int z){
        tot1++;
        a[tot1].to=y;
        a[tot1].v=z;
        a[tot1].next=head1[x];
        head1[x]=tot1;}
         
        void add_(int x,int y,int k){
        tot2++;
        que[tot2].to=y;
        que[tot2].num=k;
        que[tot2].next=head2[x];
        head2[x]=tot2;}
         
        int find(int x){
        	if(f[x]!=x)f[x]=find(f[x]);
        	return f[x];}
         
        void tarjan(int x,int fa){
        	vis[x]=1;
        	for(int i=head1[x];i;i=a[i].next){
        		if(vis[a[i].to]==0){
        		len[a[i].to]=len[x]+a[i].v;
        		tarjan(a[i].to,x);
        		f[a[i].to]=x;}}	
        	for(int i=head2[x];i;i=que[i].next){	
        		if(que[i].flag==0&&vis[que[i].to]==1){
        			que[i].flag=1;
        		ans[que[i].num]=
        		len[que[i].to]+len[x]-2*len[find(que[i].to)];}}}
         
        int main(){
        	 ios::sync_with_stdio(false);
        	 	freopen("distance.in","r",stdin);
        	freopen("distance.out","w",stdout);
        	 int n,m,q,w,e;
        	 cin>>n>>m;
        	for(int i=1;i<=n;i++)f[i]=i;
        	for(int i=1;i<=n-1;i++){
        		cin>>q>>w>>e;
        		add(q,w,e);
        		add(w,q,e);}
        	for(int i=1;i<=m;i++){
        		cin>>q>>w;
        		add_(q,w,i);
        		add_(w,q,i);}
        	tarjan(1,0);
        	for(int i=1;i<=m;i++)
        	cout<<ans[i];
        	return 0;
        }