锐客网

  1. 首页 > it技术 > >

codeforce|Codeforces Round #774 (Div. 2) D. Weight the Tree

算法思维c++图论动态规划深度优先dpcodeforce

D. Weight the Tree 题目链接
题意 | 简单
给你一棵树n n n 顶点编号从1 1 1 到n n n ，树是无环的连通无向图。
对于每个i i i =1 , 2 , . . . , n 1 , 2 , ... , n 1,2,...,n， 让 wi 是第i i i 个顶点的权值。如果一个顶点的权重等于其所有邻居的权重之和，则该顶点称为好顶点。
【codeforce|Codeforces Round #774 (Div. 2) D. Weight the Tree】最初，所有节点的权重都未分配。为树的每个顶点分配正整数权重，使得树中好顶点的数量最大化。如果有多种方法可以做到这一点，则必须找到一种使树中所有顶点的权重总和最小化的方法。
思路 | 树形dp
仔细读这道题是让我们求最大的独立集，且保持路径上权值最小。
那这样不是就贪心和黑白染色法，可以看下面这个例子codeforce|Codeforces Round #774 (Div. 2) D. Weight the Tree
文章图片

这里就要用树形dp的想法，把 d p [ ] [ ] dp[][] dp[][]定义成 p a i r pair pair类型， f i r s t first first代表的是他的下面有几个好节点， s e c o n d second second代表他下面需要多少路径的权值和。
先随便找一个点 比如1 1 1 进行深搜 ， d p [ x ] [ 0 ] dp[x][0] dp[x][0]代表当前不是好结点， d p [ x ] [ 1 ] dp[x][1] dp[x][1]代表当前是好结点，转移方程是d p [ x ] [ 1 ] . f i r s t + = d p [ t o ] [ 0 ] . f i r s t dp[x][1].first+=dp[to][0].first dp[x][1].first+=dp[to][0].first
如果当前不是好结点的话 就可以从相邻的好结点或者不是好节点转移过来 ，我们直接挑选更小的就好了
最后直接判断结点1 是好节点的值小还是普通结点的值小，在写一个d f s dfs dfs 往回找每个点的答案就行了
代码

#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long #define pii pair const int maxn = 2e5 + 100; pii dp[maxn][2]; int n; int a[maxn]; vectorg[maxn]; void dfs(int x, int f) { dp[x][0] = make_pair(0, 1); dp[x][1] = make_pair(-1, g[x].size()); //这个点被打成好结点 for (auto to : g[x]) { if (to != f) { dfs(to, x); dp[x][1].first += dp[to][0].first; dp[x][1].second += dp[to][0].second; pii tmp = min(dp[to][0], dp[to][1]); dp[x][0].first += tmp.first; dp[x][0].second += tmp.second; } } } void dfs2(int x, int f, int k) { if (k == 1) a[x] = g[x].size(); else a[x] = 1; for (auto to : g[x]) { if (to != f) { if (k ==1) dfs2(to, x, 0); else { if (dp[to][1] < dp[to][0]) dfs2(to, x, 1); else dfs2(to, x, 0); } } } } void solve() { cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } if (n == 2) { cout << 2 << " " << 2 << endl; cout << 1 << " " << 1 << endl; return; } dfs(1, 0); if (dp[1][0] < dp[1][1]) { //结点1不是好结点 cout << -dp[1][0].first <<" "<< dp[1][0].second << endl; dfs2(1, 0, 0); for (int i = 1; i <= n; i++) { cout << a[i] << " "; } cout << endl; } else { cout << -dp[1][1].first << " " << dp[1][1].second << endl; dfs2(1, 0, 1); for (int i = 1; i <= n; i++) { cout << a[i] << " "; } cout << endl; } } signed main(){ int t; t = 1; while (t--) { solve(); } return 0; } /* 8 1 4 2 4 3 4 4 5 5 6 5 7 5 8*/

    推荐阅读


    上一篇：vue|vue5 if与show

    下一篇：一天内就可以完成把PC网站改为自适应手机！就是这么简单！