1 条题解

  • 1

    #include<bits/stdc++.h>
    #define ll long long
    #define inf 0x7fffffff
    #define MOD 998244353
    using namespace std;
    const int maxn=10010;
    inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f*x;
    }

    struct edge{
    int to,pre;
    ll val;
    }G[maxn];

    int n,m,Len,cl,ans;
    int head[maxn],ins[maxn],ous[maxn],fa[maxn];
    ll tot;
    ll s[maxn];

    inline void addedge(int x,int y,ll z){G[++Len].to=y;G[Len].pre=head[x];G[Len].val=z;head[x]=Len;}
    inline void dfs(int u){
    ins[u]=++cl;
    for (int i=head[u];i;i=G[i].pre)s[G[i].to]=s[u]+G[i].val,dfs(G[i].to);
    ous[u]=cl;
    }

    int main(){
    n=read();m=read();
    int x,y;ll z;
    for (int i=1;i<n;++i){
    x=read();y=read();scanf("%lld",&z);
    fa[y]=x;
    addedge(x,y,z);
    }
    for (int i=1;i<=n;++i)if (!fa[i])dfs(i);
    ans=tot=0;
    while (m--){
    x=read();y=read();
    if (ins[x]<=ins[y]&&ins[y]<=ous[x]){
    ++ans;tot+=s[y]-s[x];
    }
    }
    printf("%d\n%lld\n",ans,tot);
    }
    全网第一个!!!!!!!!!!!!!!!!!
    袁昊轩你有什么实力!!!!!!!!!!!!!
    跪下!!!!!!!!!!!!!!!!!!!!
    @@@@@@@@@@@@

  • 1

信息

ID
1159
难度
9
分类
树结构 点击显示
标签
递交数
3
已通过
3
通过率
100%
上传者