nkoj-5974 树的难题 题解

$\texttt{Description}$

见题面。

$\texttt{Solution}$

十分套路的树形dp。

$dp_{u,i,j}$ 表示在以 $u$ 为根节点的子树中，与根节点相连的节点中有 $i$ 个黑色，$j$ 个白色，最小花费。

$dp_{u,min(1,i+x),min(2,j+y)}=min(dp_{u,i,j}+dp_{v,x,y})$。其中，$v$ 是 $u$ 的子节点。

所以大概是树形背包板题？

所以呢我特么把 $u$ 写成了 $i$，以及变量重名，调了1h

#include <cstdio>
#include <cstring>
#define int long long
#define FORAKIOI for (int i(0); i <= 1; ++ i) for (int j(0); j <= 2; ++ j)

const int INF = 1e18;

inline int min(const int x, const int y) {return x < y ? x : y;}
inline void upd(int &x, const int y) {if (x > y) x = y;}
struct Edge {
	int to, w, nxt;
} e[600005];
int head[300005], color[300005], dp[300005][2][3], tmp[2][3], tot;
inline void AddEdge(const int u, const int v, const int w) {
	e[++ tot].to = v, e[tot].w = w, e[tot].nxt = head[u], head[u] = tot;
}
void dfs(const int u, const int fa) {
	FORAKIOI dp[u][i][j] = INF;
	dp[u][0][0] = 0;
	for (int I(head[u]); I; I = e[I].nxt) if (e[I].to != fa) {
		const int v(e[I].to);
		dfs(v, u);
		FORAKIOI tmp[i][j] = INF;
		FORAKIOI
		for (int x(0); x <= 1; ++ x)
		for (int y(0); y <= 2; ++ y) {
			upd(tmp[min(1, i + x)][min(2, j + y)], dp[u][i][j] + dp[v][x][y]);
			if (x < 1 || y < 2) upd(tmp[i][j], dp[u][i][j] + dp[v][x][y] + e[I].w);
		}
		FORAKIOI dp[u][i][j] = tmp[i][j];
	}
	FORAKIOI tmp[i][j] = INF;
	FORAKIOI upd(tmp[min(1, i + (color[u] == 0))][min(2, j + (color[u] == 1))], dp[u][i][j]);
	FORAKIOI dp[u][i][j] = tmp[i][j];
}

signed main() {
	int T;
	scanf("%lld", &T);
	while (T --) {
		int n;
		memset(head, 0, sizeof head);
		memset(dp, 0x3f, sizeof dp);
		tot = 0;
		scanf("%lld", &n);
		for (int i(1); i <= n; ++ i) scanf("%lld", color + i);
		for (int i(1); i < n; ++ i) {
			int u, v, w;
			scanf("%lld%lld%lld", &u, &v, &w);
			AddEdge(u, v, w), AddEdge(v, u, w);
		}
		dfs(1, -1);
		int ans(INF);
		FORAKIOI if (i < 1 || j < 2) upd(ans, dp[1][i][j]);
		printf("%lld\n", ans);
	}
}