323. 战略游戏 (树形dp)

题目 题意: 给定n个点的树，选择最少的点，使得可以涵盖到所有的边。(不一定n-1条边，至多10*n条边) 思路: 树形dp. f[i][0]: 以i为根且选择i的最少点数的方案 f[i][1]: 以i为根且不选择i的最少点数的方案 如果选i，儿子可选可不选；如果不选i，必须选儿子(这条边一共就两个点连着，必选了) 时间复杂度: O(n) 代码:

#include
using namespace std;
int n,m,k,T;
const int N = 1502;
#define mem(a,x) memset(a,x,sizeof(a))
int h[N],e[N*20],ne[N*20],idx = 0;
void add(int a,int b)
{
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int f[1502][2]; //0:选,1:不选
int in[1502];
void dfs(int cur)
{
    f[cur][1] = 0;
    f[cur][0] = 1;
    int mn = 1e9; //哪个儿子选择代价最小
    for(int i=h[cur];~i;i=ne[i])
    {
    	int j = e[i];
    	dfs(j);
    	f[cur][1] += f[j][0];
    	f[cur][0] += min(f[j][1],f[j][0]);
    }
}
void solve()
{
	mem(h,-1); mem(in,0); idx = 0;
	for(int i=0;i