Tree dynamic programming

1582： Anniversary party

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

const int N = 6009; 
int n, p[N], h[N];
//f[u][0]： With u Root subtree , Not included u Maximum happiness 
//f[u][1]： With u Root subtree , contain u Maximum happiness 
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];					// If u Come on , be v Definitely not 
		f[u][0] += max(f[v][0], f[v][1]);	// If u Not coming , be v Come or not 
	}	
}

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： Strategy game

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

const int N = 1509; 
int n, h[N];
//f[u][0]： With u Root subtree ,u The minimum number of soldiers when the point is placed 
//f[u][1]： With u Root subtree ,u The minimum number of soldiers when clicking 
int f[N][2];		 
vector <int> e[N];

void dfs(int u) {
    
	f[u][1] = 1;							//u Place soldiers at the node  
	for (int i = 0; i < e[u].size(); i ++) {
    
		int v = e[u][i];
		dfs(v);
		
		// This question requires that each side be observed 
		// If u Place soldiers at the node , be v Nodes can be put or not  
		// If u Don't let the soldiers go , be v Nodes must be placed 
		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： A binary apple tree

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

const int N = 109; 
int n, q; 
int f[N][N];					//f[u][j]： With u Root subtree , Retain j Number of apples per branch  
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 --) {
    			// With u Reserved for the subtree of the root j root  
			for (int k = 0; k < j; k ++) {
    		// With v Reserved for the subtree of the root k root , There is another connection u and 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);									// Root node number 1, Virtual node 0 
	printf("%d", f[1][q]);
	
	return 0;
}