比赛 不准粘代码,必须自己写(HS除外) 评测结果 AAAAAAAAAA
题目名称 距离 最终得分 100
用户昵称 ShallowDream雨梨 运行时间 0.201 s
代码语言 C++ 内存使用 15.53 MiB
提交时间 2019-10-10 20:03:16
显示代码纯文本
          #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;
            }