【LA4015】Caves【Tree DP】

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2016
제목:
n개의 점의 나무 한 그루가 뿌리 노드에서 출발하면 노정이 s를 넘지 않고 최대 몇 개의 점을 두루 돌아다닐 수 있습니까?
대백의 문제.그래도 괜찮은데 tree dp.
dp[u][x][0]를 설정하면 u의 서브트리에서 u에서 출발하여 x개의 노드를 지나 u의 노정으로 돌아가지 않는다.
dp[u][x][1]을 설정하면 u의 서브트리에서 u에서 출발하여 x개의 노드를 지나 u의 노정으로 돌아간다.v를 u의 아들로 설정하고,len을 (u,v) 이 변의 길이로 설정합니다.
dp[u][x][0]의 경우
첫 번째, 먼저 v의 서브트리에서 i 노드를 걷고 u로 돌아간 다음에 다른 서브트리에서 u로 돌아가지 않으면 dp[u][x][0]=dp[v][i][1]+len*2+dp[u][x-i][0]가 있다.
두 번째, 먼저 다른 나무에 가서 u로 돌아간 다음에 v의 나무에 가서 i개의 노드를 걷는다. 그러면 dp[u][x][0]=dp[u][x-i][1]+len+dp[v][i][0]가 있다.
dp[u][x][1]의 경우
다른 서브트리와 v의 서브트리를 지나 v의 서브트리에서 i개의 노드를 걷고 u로 돌아가면 dp[u][x][1]=dp[v][i][1]+dp[u][x-i][1]+len*2가 있다.
방정식은 01배낭과 유사하기 때문에 x는 큰 것에서 작은 것까지 매거해야 한다.
실수로 출력에 Case가 하나 더 있어서 와라발...
멍하다. 비록 문제에서 0이 뿌리 노드라고 말하지 않았지만 데이터에서 확실히 0이 뿌리 노드이다.그래서 도수조를 하나 줄일 수 있다.

/* Footprints In The Blood Soaked Snow */
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 505, maxm = maxn, inf = 0x3f3f3f3f;

int n, head[maxn], cnt, size[maxn], dp[maxn][maxn][2];

struct _edge {
	int v, w, next;
} g[maxm << 1];

inline int iread() {
	int f = 1, x = 0; char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;
	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	return f * x;
}

inline void add(int u, int v, int w) {
	g[cnt] = (_edge){v, w, head[u]};
	head[u] = cnt++;
}

inline void dfs(int u) {
	size[u] = 1;
	dp[u][1][0] = dp[u][1][1] = 0;
	for(int i = head[u]; ~i; i = g[i].next) {
		int v = g[i].v;
		dfs(v);
		size[u] += size[v];
		for(int x = size[u]; x > 0; x--) for(int j = 1; j <= size[v]; j++) {
			if(x - j < 1) break;
			dp[u][x][0] = min(dp[u][x][0], min(dp[v][j][1] + dp[u][x - j][0] + g[i].w * 2, dp[v][j][0] + dp[u][x - j][1] + g[i].w));
			dp[u][x][1] = min(dp[u][x][1], dp[v][j][1] + dp[u][x - j][1] + g[i].w * 2);
		}
	}
}

int main() {
	for(int cas = 1; ; cas++) {
		n = iread();
		if(!n) break;

		for(int i = 0; i <= n; i++) head[i] = -1; cnt = 0;
		for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) dp[i][j][0] = dp[i][j][1] = inf;

		for(int i = 1; i < n; i++) {
			int u = iread(), v = iread(), w = iread(); u++; v++;
			add(v, u, w);
		}

		dfs(1);

		printf("Case %d:
", cas);
		int T = iread();
		while(T--) {
			int s = iread(), ans = 0;
			for(int i = 0; i <= n; i++) if(dp[1][i][0] <= s || dp[1][i][1] <= s) ans = i;
			printf("%d
", ans);
		}
	}
}