60分求助
查看原帖
60分求助
542698
封禁用户楼主2022/12/25 12:14
#include<bits/stdc++.h>
using namespace std;
int n,h,f[100005],g[100005],head[100005],to[200005],len[200005],Next[200005],num;
void build(int u,int v,int l)
{
    Next[++num]=head[u];
    head[u]=num;
    to[num]=v;
    len[num]=l;
}
void dfs(int now,int fa)
{
    int son=0,tot=0;
    for(int i=head[now];i;i=Next[i])
    {
        int j=to[i];
        if(j==fa)
        {
            tot=i;
            continue;
        }
        if(len[i]>=h)
        {
            printf("No solution.\n");
            exit(0);
        }
        dfs(j,now);
        g[now]=max(g[now],len[i]+g[j]);
        f[now]+=f[j];
        son++;
    }
    if(!son)
    {
        f[now]=0;
        g[now]=1;
    }
    else
    {
        if(son!=1&&g[now]+len[tot]>h)
        {
            f[now]++;
            g[now]=1;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int temp;
        scanf("%d",&temp);
        for(int j=1;j<=temp;j++)
        {
            int v,l;
            scanf("%d %d",&v,&l);
            build(i,v,l);
        }
    }
    scanf("%d",&h);
    dfs(1,0);
    printf("%d\n",f[1]);
    return 0;
}
2022/12/25 12:14
加载中...