传送门

题目大意：

给一颗二叉树染色红绿蓝，父亲和儿子颜色必须不同，两个儿子颜色必须不同，问最多和最少能染多少个绿色的、

题目分析：

裸的树型dp：\(dp[u][col][type]\)表示u节点染为col(0-绿色，1-红色，2-蓝色)，当前求的是type（0-最小，1-最大）解。

然后最后输出最大为\(max(dp[1][0][1], dp[1][1][1], dp[1][2][1])\)，最小为\(min(dp[1][0][0], dp[1][1][0], dp[1][2][0])\)。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 500005, oo = 0x3f3f3f3f;

vector<int> adj[N];

int tot, dp[N][3][2];

inline void read(int k){

	int t, v; char tt; scanf("%c", &tt);

	t = tt - '0';

	for(int i = 1; i <= t; i++){

		adj[k].push_back(v = ++tot);

		read(v);

	}

}

inline int DP(int u, int f, int col, int type){

	if(dp[u][col][type] != -1) return dp[u][col][type];

	dp[u][col][type] = col == 0 ? 1 : 0;

	if(!adj[u].size()) return dp[u][col][type];

	int col1, col2;   //另外两种

	if(col == 0) col1 = 1, col2 = 2;

	else if(col == 1) col1 = 0, col2 = 2;

	else col1 = 0, col2 = 1;

	if(adj[u].size() == 1){   //只有一个儿子

		int v = adj[u][0];

		if(type == 1)

			dp[u][col][type] += max(DP(v, u, col1, type), DP(v, u, col2, type));

		else dp[u][col][type] += min(DP(v, u, col1, type), DP(v, u, col2, type));

	}

	else{                   //只有两个儿子

		int v1 = adj[u][0], v2 = adj[u][1];

		int t1 = DP(v1, u, col1, type) + DP(v2, u, col2, type);

		int t2 = DP(v1, u, col2, type) + DP(v2, u, col1, type);

		if(type == 1)

			dp[u][col][type] += max(t1, t2);

		else dp[u][col][type] += min(t1, t2);

	}

	return dp[u][col][type];

}

int main(){

	read(tot = 1);

	memset(dp, -1, sizeof dp);

	int ans1 = -1, ans2 = oo;

	for(int i = 0; i < 3; i++)

		ans1 = max(ans1, DP(1, 0, i, 1)), ans2 = min(ans2, DP(1, 0, i, 0));

	printf("%d %d", ans1, ans2);

	return 0;

}