Weight the Tree(树形dp/记忆化搜索)

题目 题意：给定一棵树，现给树上的每个结点一个权值。定义一个结点为好的结点，如果它的权值，等于周围相连结点的权值之和。求最多的好的结点的数量，以及对应的最少需要的权值。输出每个结点的权值。

参考 对于结点数为2的树，特殊考虑下，此时取1 1，即可满足题意。 对结点数不为2的情况，我们可以发现，相邻的结点不能同时都为好结点。因此，题目转化为求树上不相邻的最大的独立集。求出独立集后，为使权值总和最小，我们给树上每个非好结点赋值为1，则好结点的权值，则为它们的相邻的结点数量（即相连的边的数量）。

#include
using namespace std;
#define ll long long
const int maxn = 200010;

vector g[maxn];
pair dp[maxn][2];
int ans[maxn];
int fa[maxn];
int n, u, v;

/* f(u,x) = dp[u][x] 表示以u为结点的子树， 
   且u取(x==1)/不取(x!=1)为好结点，
   的最大好结点数量
   返回  
*/ 
pair f(int u, int x) {
	if (dp[u][x].first != -1) {
		return dp[u][x];
	}
	dp[u][x].first = x;
	dp[u][x].second = x ? (int)g[u].size() : 1;
	// 为方便比较大小，需要的最小权值，用负数存储 
	dp[u][x].second = -dp[u][x].second;
	
	pair son;
	// 父结点为good node时，子节点不能取good node 
	for (auto v: g[u]) {
		if (fa[u] == v) {
			continue;
		}
		fa[v] = u;
		if (x) {// 父节点为 good node 
			son = f(v, 0);
		} else {
			son = max(f(v, 0), f(v, 1));
		}
		dp[u][x].first += son.first;
		dp[u][x].second += son.second;
	}
	
	return dp[u][x];
}

void cal(pair p, int u) {
	if (dp[u][0] == p) {
		ans[u] = 1;
		for (auto v: g[u]) {
			if (fa[u] == v) continue;
			cal(max(dp[v][0], dp[v][1]), v);
		}
	} else {
		ans[u] = (int)g[u].size();
		for (auto v: g[u]) {
			if (fa[u] == v) continue;
			cal(dp[v][0], v);
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1;i