E

// f[u][0] u 位置不放置士兵
// f[u][1] u 位置放置士兵

// u 和 v 之间有一条边，u 没有士兵，v必须有
// f[u][0] += f[v][1]

// u 这个点已经有了， v 有没有无所谓
//f[u][1] += min(f[v][0] , f[v][1])

A

// f[i][2] 以 i 为根的子树的最大值，0 代表不来， 1 代表来
// f[i][2]  i 的所有子节点
// 上司不来， 下属可以来或者不来
// f[i][0] +=  max(f[son[i]][0] , f[son[i]][1])
// 上司来， 下属不能来
// f[i][1] += f[son[i]][0]
#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
const int M = N * 2;
int n, r[N];
int head[N], ver[M], nxt[M], tot;
int f[N][2];

void add(int u, int v) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

void dfs(int u, int fa) {
	f[u][1] = r[u];
	// 遍历所有子节点
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa)
			continue;
		dfs(v, u);
		// 上司不来， 下属可以来或者不来
		f[u][0] += max(f[v][0], f[v][1]);
		// 上司来， 下属不能来
		f[u][1] += f[v][0];
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> r[i];
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	dfs(1, 0);
	cout << max(f[1][0], f[1][1]);
	return 0;
}

B

// f[i][j] 以 i 为根,选择 j 门课程
//  的最大学分
// f[i][j] = max(f[i][j-k] + f[v][k])

// 森林， 加一个 root 节点
// m ，加上root 节点， m+1 门课
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
const int M = N * 2;
int a[N];
int f[N][N];
int n, m;
int  siz[N];
int head[N], ver[M], nxt[M], tot;
void add(int u, int v) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

void dfs(int u, int fa) {
	f[u][1] = a[u];  // 学一门，只能是学自己
	siz[u] = 1;
	for (int i = head[u] ; i; i = nxt[i]) {
		int v = ver[i];
		if (v == fa)
			continue;
		dfs(v, u);
		siz[u] += siz[v];
		// 分组背包
		for (int j = min(m, siz[u]) ; j >= 1; j-- ) {
			// u 这个点是必须放的 -1
			for (int k = 0 ; k <= min(j - 1, siz[v]) ; k++)
				f[u][j] = max(f[u][j], f[v][k] + f[u][j - k]);
		}
	}
}

int main() {
	cin >> n >> m;
	m++; // root
	for (int i = 1 ; i <= n; i++) {
		int x;
		cin >> x >> a[i];
		// 如果 x  为0，直接当做根节点，不用管
		add(x, i), add(i, x);
	}
	dfs(0, -1);
	cout << f[0][m];
	return 0;
}

T

// 换根DP
// f[v] = f[u] - siz[v]-n - siz[v]
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = N * 2;
#define int long long
int n;
int  siz[N], dep[N], f[N];
int head[N], ver[M], nxt[M], tot;

void add(int u, int v) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

void dfs(int u, int fa) {
	dep[u] = dep[fa] + 1;
	siz[u] = 1;
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa)
			continue;
		dfs(v, u);
		siz[u] += siz[v];
	}
}

void dp(int u, int fa) {
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa)
			continue;
		f[v] = f[u] - 2 * siz[v] + n;
		dp(v, u);
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++)
		f[1] += dep[i];
	dp(1, 0);
	int res = 1;
	for (int i = 2; i <= n; i++)
		if (f[i] > f[res])
			res = i;
	cout << res;
	return 0;
}