树形DP入门题萌新求助

qip101 @ 2022-08-09 15:25:47

#include <iostream>
#include <cstdio>
#include <cstdlib> 
#include <algorithm>
#include <vector>
#define MAXN 5050
using namespace std;
int n,f[MAXN][5];
vector <int> G[MAXN];
inline void dfs(int u,int fa)
{
    f[u][0]=0;f[u][1]=1;
    for(register int i=1;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa) 
            continue;
        dfs(v,u);
        f[u][0]+=f[v][1];
        f[u][1]+=min(f[u][1],f[u][0]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    while(n--)
    {
        int u,k;
        cin >> u >> k;
        for(register int i=1;i<=k;i++)
        {
            int v;
            cin >> v;
            G[u].push_back(v);
        }
    }
    dfs(0,-1);
    cout << min(f[0][0],f[0][1]) << endl;
    return 0;
}

by ShuKuang @ 2022-08-09 15:31:36

by qip101 @ 2022-08-09 15:33:51

@ShuKuang 不对不是这个问题

by qip101 @ 2022-08-09 15:34:36

样例过了但是全WA了

#include <bits/stdc++.h> 
#define MAXN 5050
using namespace std;
int n,f[MAXN][2];
vector <int> G[MAXN];
inline void dfs(int u,int fa)
{
    f[u][0]=0;f[u][1]=1;
    for(register int i=1;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa) 
            continue;
        dfs(v,u);
        f[u][0]+=f[v][1];
        f[u][1]+=min(f[u][1],f[u][0]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    while(n--)
    {
        int u,k;
        cin >> u >> k;
        for(register int i=1;i<=k;i++)
        {
            int v;
            cin >> v;
            G[u].push_back(v);
        }
    }
    dfs(1,0);
    cout << min(f[1][0],f[1][1]) << endl;
    return 0;
}