前言：好久没有写树上dp了，这儿题目还是挺有意思的
题目地址
#include<bits/stdc++.h>
#include<iostream>
using namespace std;//#define int long long
int n;
const int N = (int)1e5+10;
int e[N],ne[N],h[N],idx = 0;
int dp[2][N];void add(int a,int b){e[++idx] = b; ne[idx] = h[a]; h[a] = idx;
}void dfs(int node,int fa){dp[1][node] = 1 , dp[0][node] = 0;for(int i=h[node];i;i=ne[i]){int to = e[i];if(to==fa) continue;dfs(to,node);dp[0][node] += dp[1][to];dp[1][node] += min(dp[0][to],dp[1][to]);}
}signed main(){cin >> n;for(int i=0;i<n;i++){int now,num; cin >> now >> num;now++;for(int j=1;j<=num;j++){int u; cin >> u; u++;add(now,u); add(u,now);}}dfs(1,-1);cout << min(dp[0][1],dp[1][1]);system("pause");return 0;
}
再来一个双倍经验的题目
题目地址
