#|【CF1646D】D. Weight the Tree（树形dp、贪心）树|算法|dfs|动态规划|贪心算法

加权树
题意：

给定一颗树，让你给树上的点赋予权值。定义一个点的权值等于其所有相邻节点的权重之和时，这个点就是 good。
你需要找到一种赋值方法，使得树中 good 点数最多，同时所有顶点的权重总和最小。

【#|【CF1646D】D. Weight the Tree（树形dp、贪心）】思路：

可以发现，除了单独两个点一条边的情况，这两个点都赋值为 1，都是 good，其他情况下，树中任意相邻两点不可能同时都是 good。画下图就能看出来。当时完全没往这方面想…
这就启发我们，去维护一个树上最大独立集（最大点集同时点集中的点之间没有边）
这完全可以用树形dp 的思想去维护，用d p [ i ] [ 2 ] dp[i][2] dp[i][2] 表示某个结点选还是不选能得到的某某值。可以证明这样维护是能涵盖所有情况的。
状态集合清楚了，剩下还有赋值的问题，贪心地想，不是 good 的点我们都赋值最小值也就是 1，good 点周围都是非 good 点，自然赋值就是相连的点数。
此题除了要维护最大 good 数，还要维护最小权重和。所以我们的 dp 数组开成 pair 类型，优先维护 good，good 相同时维护权重即可。
最后只需要根据 dp 性质反推方案。

C o d e : Code: Code:

#include #include #define mem(a,b) memset(a,b,sizeof a) #define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)) #define sca scanf #define pri printf #define forr(a,b,c) for(int a=b; a<=c; a++) #define rfor(a,b,c) for(int a=b; a>=c; a--) #define all(a) a.begin(),a.end() #define oper(a) (operator<(const a& ee)const) #define endl "\n" using namespace std; typedef long long ll; typedef pair PII; double DNF = 1e17; const int N = 200010, M = 400010, MM = 110; int INF = 0x3f3f3f3f, mod = 1e9 + 7; ll LNF = 0x3f3f3f3f3f3f3f3f; int n, m, k, T, S, D, K; vector e[N]; PII dp[N][2]; //dp[i][1]表示选择该点，dp[i][0]表示不选该点 //PII的一维维护最大良好顶点个数，二维维护最小顶点权重总和 // //一个维护最大一个维护最小，有点不方便 //这里反转了一下，维护最小良好顶点个数，在最后的时候取负回正就行 int g[N]; void dfs_pre(int x, int fa) { dp[x][0] = { 0,1 }; //该点不选，贪心的想，权重为 1 dp[x][1] = { -1,e[x].size() }; //选了的话，个数 1，权值为相连点数（毕竟它们权重都是 1） for (int j : e[x]) { if (j == fa)continue; dfs_pre(j, x); //当前点选的情况只能由全部子节点不选转移过来 dp[x][1].first += dp[j][0].first; dp[x][1].second += dp[j][0].second; //不选的情况，就可以根据情况转 //优先最大化良好顶点的数量，数量相同选权值最小 //这个过程因为我们之前反转了一维定义，所以可以直接用 PII 取 min //PII 取 min 的过程就是优先处理一维，相同再更新二维PII tmp = min(dp[j][0], dp[j][1]); dp[x][0].first += tmp.first; dp[x][0].second += tmp.second; } }void dfs_find(int x, int fa, int c) { //c表示该点选还是不选 if (c == 1)g[x] = e[x].size(); else g[x] = 1; for (int j : e[x]) { if (j == fa)continue; if (c == 1)dfs_find(j, x, 0); //选只能由不选转移过来 else { //否则找个小的转移 if (dp[j][1] < dp[j][0])dfs_find(j, x, 1); else dfs_find(j, x, 0); } } }void solve() { cin >> n; forr(i, 1, n - 1) { int a, b; cin >> a >> b; e[a].push_back(b); e[b].push_back(a); } if (n == 2) { //当且仅当两个顶点一条边的时候，很特殊，两点都是良好点 cout << "2 2\n1 1"; return; } //否则树中良好点必定不相邻，也就变成了最大独立集问题 //可用选和不选的思路去树形dp，可以证明这样包含了所有情况 dfs_pre(1, -1); //判断下选哪个更优，然后递归输出方案即可 if (dp[1][1] < dp[1][0]) { cout << -dp[1][1].first << ' ' << dp[1][1].second << endl; dfs_find(1, -1, 1); forr(i, 1, n)cout << g[i] << ' '; } else { cout << -dp[1][0].first << ' ' << dp[1][0].second << endl; dfs_find(1, -1, 0); forr(i, 1, n)cout << g[i] << ' '; } }int main() { cinios; T = 1; while (T--)solve(); return 0; } /* */

DP顶真，鉴定为：好题