[TIOJ] 1711. Apple Tree

題目連結:http://tioj.infor.org/problems/1711

---

說個笑話，oToToT會寫程式。
搞了好久都不會做，然後一直假解QAQ
去網路上查到momo學長的解居然也是錯的（詳見底下測資）

10 6
522 288 963 788 756 856 18 412 378 789
2 1
3 2
4 2
5 2
6 5
7 6
8 4
9 1
10 4

最後是去問了minson才知道一個怪怪的解QQ，我到現在還是不知道這為何是好的(他說複雜度是$O(N^2)$)，可能跟CF 729F有類的概念吧。
註(2019/04/24):似乎是因為某種兩個東西只會在他們的LCA被合起來
總之就是用一個顯然的事實就是我們一個(子)樹最多只能走他底下size步，所以我們就只要維護size，並且每次上界都用當前大小做dp即可。
dp狀態也很簡單 $ dp[i][j][0] := \text{第i個節點走j步後且要走回來的最大值}, dp[i][j][1] := \text{第i個節點走j步後，停在他底下某個人的最大值} $轉移就直接暴力混和背包即可。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
const int N = 1000 + 5;

int w[N], dp[N][N<<1][2];
int tmp[N<<1][2], sz[N];
std::vector<int> G[N];

void dfs(int,int,int);

int main(){
	int n, k; scanf("%d%d", &n, &k); k = std::min(k, n+n);
	for(int i=1;i<=n;i++) scanf("%d", w+i);
	for(int i=1;i<n;i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dp[1][0][0] = dp[1][0][1] = w[1];
	dfs(1, 1, k); int ans = 0;
	for(int i=0;i<=k;i++) ans = std::max(ans, dp[1][i][1]);
	printf("%d\n", ans);
	return 0;
}

void dfs(int u, int f, int k) {
	sz[u] = 1;
	for(int v: G[u]) if(v != f) {
		dfs(v, u, k);
		for(int i=0;i<=std::min(sz[u]+sz[u]+sz[v]+sz[v], k);i++) {
			tmp[i][0] = dp[u][i][0];
			tmp[i][1] = dp[u][i][1];
		}
		for(int i=0;i<=sz[u]+sz[u];i++){
			for(int j=0;j<=sz[v]+sz[v];j++){
				if(i + j + 2 > k) break;
				tmp[i+j+2][0] = std::max(tmp[i+j+2][0], dp[u][i][0]+dp[v][j][0]+w[v]);
				tmp[i+j+2][1] = std::max(tmp[i+j+2][1], dp[u][i][1]+dp[v][j][0]+w[v]);
			}
			for(int j=0;j<=sz[v]+sz[v];j++) {
				if(i + j + 1 > k) break;
				tmp[i+j+1][1] = std::max(tmp[i+j+1][1], 
						dp[u][i][0]+dp[v][j][1]+w[v]);
			}
		}
		for(int i=0;i<=std::min(sz[u]+sz[u]+sz[v]+sz[v], k);i++) {
			dp[u][i][0] = tmp[i][0];
			dp[u][i][1] = tmp[i][1];
		}
		sz[u] += sz[v];
	}
}