第7个测试点有毒吧

/*我的思路是这样的:将每个节点的父节点保存在数组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 条评论

目前还没有评论...

信息

ID
1071
难度
7
分类
树结构 点击显示
标签
递交数
61
已通过
12
通过率
20%
上传者