2024年CCPC网络赛C题题解 —— 种树（gym105336C）

大家好，欢迎来到IT知识分享网。

      一道不错的树形dp题，想要提升树形dp的糕手们可以做一下，放上题面：

     题意：给你一个有0有1的数，每次可以把一个大小为3（包含3个结点）的结构中，要求至少包含一个1，然后就能把整个块的结点都变成1，问你最少需要这样几次操作能使所有节点都变成1。

    然后赛时其实我没做出来，树形dp这个做法是想到的，但是被J这个线性基卡住了（本人当时没接触过线性基），然后一些题目没有去写。所以我先来讲讲树形dp的解法：

     我们来观察一下，如果这个结构大小要求的是2，那么其实可以直接设置一个有关父节点和子节点的状态转移的dp（这玩意应该比较好想），这道题目如果是大小为3的话，我们可以这样子设置一个dp的状态转移：考虑树形 DP，对于一个子树而言，最多可能有 4 种情况：贡献 1 个给父亲、不需要父亲贡献、父亲贡 献 1 个给该子树、父亲贡献 2 个给该子树。 那么，设 fu,−1/0/1/2 分别表示子树 u 对应的这些情况。转移时考虑枚举 u 所有儿子 v 的情况，注意一 下 u 自己本身是否已经种上树、以及两个 fv1,1、fv2,1 可以合并（即使用一次操作完成）的情况即可。 实现细节可能较多。然后实现的代码是这样的：

#include<bits/stdc++.h> #define Alex std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0); #define int long long #define double long double const int QAQ = 0; const int mod = ; const double pi = std::acos(-1.0); const double eps = 1e-10; int n,m,p[],f[][4],g[2][2],h[2][2]; std::vector<int> G[]; inline void dfs(int u,int fa) { for(auto v : G[u]) { if(v == fa) continue; dfs(v,u); } for(int i = 0;i <= 1;i++) for(int j = 0;j <= 1;j++) g[i][j] = 2e18; g[0][p[u]] = 0; for(auto v : G[u]) { if(v == fa) continue; for(int i = 0;i <= 1;i++) for(int j = 0;j <= 1;j++) { h[i][j] = g[i][j]; g[i][j] = g[i][j] + f[v][0]; } for(int i = 0;i <= 1;i++) { g[0][i] = std::min(g[0][i],h[1][i] + f[v][1] + 1); g[1][i] = std::min(g[1][i],h[0][i] + f[v][1]); } for(int i = 0;i <= 1;i++) for(int j = 0;j <= 1;j++) g[i][1] = std::min(g[i][1],h[i][j] + f[v][2]); } f[u][0] = std::min(g[0][1],g[1][0] + 1); f[u][1] = g[0][0]; f[u][2] = std::min(g[0][0],g[1][1]) + 1; } signed main() { Alex; int _; _ = 1; std::cin>>_; while(_--) { std::cin>>n>>m; for(int i = 0;i <= n + 5;i++) for(int j = 0;j <= 2;j++) f[i][j] = 2e18; for(int i = 0;i <= 1;i++) for(int j = 0;j <= 1;j++) { g[i][j] = h[i][j] = 2e18; } for(int i = 0;i <= n + 5;i++) p[i] = 0; for(int i = 1;i <= m;i++) { int x; std::cin>>x; p[x] = 1; } for(int i = 0;i <= n + 5;i++) G[i].clear(); for(int i = 1;i <= n - 1;i++) { int u,v; std::cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } dfs(1,0); std::cout<<std::min(f[1][0],f[1][2])<<'\n'; } return QAQ; } 

第二种做法是贪心：贪心做法 对于一次操作，最多完成两个未完成的节点。 对于一个大小为 siz 的子树，且只有根节点完成了，那么一共需要  siz / 2 次操作。 对子树根节点是否完成进行分类讨论： • 如果根节点已经完成了，那么这个子树对根节点父亲的贡献就有两种情况：用最少次数做完子树 时，是否存在多余的、且对子树根节点的父亲有贡献的操作。 如果根节点没有完成，则直接将 siz 向上传递。直到遇到一个已经完成的祖先，在那个祖先中对 siz 进行统计即可。 总的时间复杂度为 O(n)。这种做法的代码实现是这样的：

#include<bits/stdc++.h> #define Alex std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0); #define int long long #define double long double const int QAQ = 0; const int mod = 1e9 + 7; const double pi = std::acos(-1.0); const double eps = 1e-10; int f[]; bool p[]; std::vector<int> G[]; int n,m,ans = 0; inline void Fre() { int liujiahui = ; } inline int dfs(int u,int fa) { int res = 0; for(auto v : G[u]) { if(v == fa) continue; f[v] = dfs(v,u); } for(auto v : G[u]) { if(v == fa || p[v] == 0) continue; int t = f[v]; if(p[u] == 0 && t != 0) p[u] = 1; } for(auto v : G[u]) { if(v == fa || p[v] == 1) continue; int t = f[v]; res += t; } if(p[u] == 0) { res++; return res; }else { ans = ans + (res + 1) / 2; return res & 1; } } signed main() { Alex; int _; _ = 1; std::cin>>_; while(_--) { std::cin>>n>>m; for(int i = 0;i <= n + 5;i++) p[i] = 0; for(int i = 0;i <= n + 5;i++) f[i] = 0; for(int i = 0;i <= n + 5;i++) G[i].clear(); for(int i = 1;i <= m;i++) { int x; std::cin>>x; p[x] = 1; } for(int i = 1;i <= n - 1;i++) { int u,v; std::cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } ans = 0; int res = dfs(1,0); if(p[1] == 0) ans = ans + (res + 1) / 2; std::cout<<ans<<'\n'; } return QAQ; }