题意
给你n个节点的树，让你给每个节点进行赋值，并且赋的值需要为正整数；
同时当一个节点的值等于所有邻居节点的值的和时，这个点为好点；
求出一组赋值情况，满足树的好点个数最大化的同时，所有节点赋值的总和最小；
思路1. 显然无法存在两个好点相邻存在的情况（除非只有两个节点）；
2. 对于坏点直接赋值为1即可；
3. 可以树形dp解决，f[x][0/1][0/1]，第一维代表以x为根，第二维代表是否为好点，第三维代表是好点的个数/子树节点值的总和
代码
#includeusing namespace std;vector g[200005];int f[200005][2][2];long long ans[200005];int cnt[200005];void dp(int x, int fa) { f[x][1][0] = 1;//好点个数 f[x][1][1] = g[x].size();//累计 f[x][0][0] = 0; f[x][0][1] = 1; for (auto k: g[x]) { if (k == fa)continue; dp(k, x); } for (auto k: g[x]) { if (k == fa)continue; f[x][1][0] += (f[k][0][0]); f[x][1][1] += (f[k][0][1]); } for (auto k: g[x]) { if (k == fa)continue; if (f[k][0][0] > f[k][1][0]) { f[x][0][0] += f[k][0][0]; f[x][0][1] += f[k][0][1]; } else if (f[k][0][0] == f[k][1][0]) { f[x][0][0] += f[k][0][0]; f[x][0][1] += min(f[k][0][1], f[k][1][1]); } else { f[x][0][0] += f[k][1][0]; f[x][0][1] += f[k][1][1]; } }}void down(int x, int fa, int now) { ans[x] = now; if (now == 1) { for (auto k: g[x]) { if (k == fa)continue; down(k, x, 0); } } else { for (auto k: g[x]) { if (k == fa)continue; if (f[k][0][0] > f[k][1][0]) { down(k, x, 0); } else if (f[k][0][0] == f[k][1][0]) { if (f[k][0][1] > n;// for (int i = 1; i <= n; i++)g[i].clear(), f[i] = 0, ans[i] = 0; for (int i = 1; i > x >> y; g[x].emplace_back(y); g[y].emplace_back(x); } if (n == 2) { cout << 2 << ' ' << 2 << '\n'; cout << 1 << ' ' << 1 < f[1][1][0])flag = 0; if (f[1][0][0] == f[1][1][0] && f[1][0][1] < f[1][1][1])flag = 0; down(1, 0, flag); cout << f[1][flag][0] << ' ' << f[1][flag][1] << '\n'; for (int i = 1; i <= n; i++) { if (ans[i])cout << g[i].size() << ' '; else cout << 1 << ' '; }}int main() { run(); return 0;}