树形动态规划

1582：周年纪念晚会

#include <bits/stdc++.h>
using namespace std;

const int N = 6009; 
int n, p[N], h[N];
//f[u][0]：以u为根的子树，不含u的最大快乐度
//f[u][1]：以u为根的子树，包含u的最大快乐度
int f[N][2];		 
vector <int> e[N];

void dfs(int u) {
    
	f[u][1] = p[u];
	for (int i = 0; i < e[u].size(); i ++) {
    
		int v = e[u][i];
		dfs(v);
		
		f[u][1] += f[v][0];					//如果u来，则v一定不来
		f[u][0] += max(f[v][0], f[v][1]);	//如果u不来，则v可来可不来
	}	
}

int main() {
    
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) scanf("%d", &p[i]);
	
	int l, k;
	while (scanf("%d%d", &l, &k) && l || k) {
    
		e[k].push_back(l);
		h[l] = 1;
	}
	
	int root;
	for (int i = 1; i <= n; i ++) {
    
		if (!h[i]) {
    
			root = i;
			break;
		}
	}

	dfs(root);
	printf("%d", max(f[root][0], f[root][1]));
	
	return 0;
}

1578：战略游戏

#include <bits/stdc++.h>
using namespace std;

const int N = 1509; 
int n, h[N];
//f[u][0]：以u为根的子树，u点放置时的最小士兵数
//f[u][1]：以u为根的子树，u点不放时的最小士兵数
int f[N][2];		 
vector <int> e[N];

void dfs(int u) {
    
	f[u][1] = 1;							//u结点放置士兵 
	for (int i = 0; i < e[u].size(); i ++) {
    
		int v = e[u][i];
		dfs(v);
		
		//本题要求每条边都被观察到
		//如果u结点放置士兵，则v结点可放可不放 
		//如果u结点不放士兵，则v结点必须放
		f[u][1] += min(f[v][0], f[v][1]);
		f[u][0] += f[v][1];
	}	
}

int main() {
    
	scanf("%d", &n);
	for (int i = 0; i < n; i ++) {
    
		int u, k, r;
		scanf("%d%d", &u, &k);
		for (int j = 1; j <= k; j ++) {
    
			scanf("%d", &r);
			e[u].push_back(r);
			h[r] = 1;
		}
	}
	
	int root;
	for (int i = 0; i < n; i ++) {
    
		if (!h[i]) {
    
			root = i;
			break;
		}
	}
	
	dfs(root);
	printf("%d", min(f[root][0], f[root][1]));
	
	return 0;
}

1575：二叉苹果树

#include <bits/stdc++.h>
using namespace std;

const int N = 109; 
int n, q; 
int f[N][N];					//f[u][j]：以u为根的子树，保留j根树枝的苹果数量 
vector <pair<int, int> > e[N];	//to, weight

void dfs(int u, int fa) {
    
	for (int i = 0; i < e[u].size(); i ++) {
    
		int v = e[u][i].first;
		int w = e[u][i].second;
		if (v == fa) continue;
		dfs(v, u);
		
		for (int j = q; j > 0; j --) {
    			//以u为根的子树保留j根 
			for (int k = 0; k < j; k ++) {
    		//以v为根的子树保留k根，另有一根连接u和v 
				f[u][j] = max(f[u][j], f[u][j - 1 - k] + f[v][k] + w);
			}
		}
	}	
}

int main() {
    
	scanf("%d%d", &n, &q);
	for (int i = 1; i < n; i ++) {
    
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		e[u].push_back(make_pair(v, w));
		e[v].push_back(make_pair(u, w));
	}
	
	dfs(1, 0);									//根结点编号1，虚拟结点0 
	printf("%d", f[1][q]);
	
	return 0;
}