- 拉力赛
- 2021-01-26 13:22:25 @
/*我的思路是这样的:将每个节点的父节点保存在数组fa[]中,将每个节点到父节点的边权保存在edge[]数组中,对于查询<u,v>,地柜查找节点 v 的父节点,如果u是其中一个父节点,就能到达,否则当查到根节点就结束。*/
//#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=10005;
int n,m,a,b,t,u,v;
int fa[MAXN],edge[MAXN];
int fau=0;
long long edgeSum=0,ans1=0;
long long timeCount=0,ans2=0;
int solve(){
fau=fa[u];
int y=v;
int x;
int fay=fa[y];//避免多次查找数组
while( fay!=-1){
if(fay==u){//找到答案
timeCount+=edge[y];
break;
}
if(fay==fau){//算是一点小小的优化吧
timeCount=0;
return -1;
}
timeCount+=edge[y];
//edgeSum++;
x=fay;
y=x;
fay=fa[y];
}
if(fa[y]==-1){
timeCount=0;
//edgeSum=0;
return -1;
}
return 1;
}
int main(){
freopen("data.in", "r", stdin);
//cin>>n>>m;
scanf("%d%d",&n,&m);
for(int i=0; i<n-1; i++){
//cin>>a>>b>>t;
scanf("%d%d%d",&a,&b,&t);
if(i==0)fa[a]=-1;
fa[b]=a;//b的父节点是a
edge[b]=t;//节点 b 到 父节点的边权为 t
}
for(int i=0; i<m; i++){
//cin>>u>>v;
scanf("%d%d",&u,&v);
if(solve()==1)ans2++;
ans1+=timeCount;
timeCount=0;
//ans2+=edgeSum;
}
//cout<<ans2<<endl<<ans1;
printf("%d\n%d",ans2,ans1);
return 0;
}
0 条评论
目前还没有评论...