比赛 |
不准粘代码,必须自己写(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;
}