题解：洛谷 P2996 [USACO10NOV] Visiting Cows G

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2996 [USACO10NOV] Visiting Cows G【题目描述】经过了几周的辛苦工作Bessie 终于迎来了一个假期。作为奶牛群中最会社交的牛她希望去拜访N ( 1 ≤ N ≤ 50000 ) N(1 \le N \le 50000)N(1≤N≤50000)个朋友。这些朋友被标号为1 , 2 , … , N 1,2,\dots,N1,2,…,N。这些奶牛有一个不同寻常的交通系统里面有N − 1 N-1N−1条路每条路连接了一对编号为C 1 C_1C1​和C 2 C_2C2​的奶牛( 1 ≤ C 1 ≤ N , 1 ≤ C 2 ≤ N , C 1 ≠ C 2 ) (1 \le C_1 \le N, 1 \le C_2 \le N, C_1 \ne C_2)(1≤C1​≤N,1≤C2​≤N,C1​C2​)。这样在每一对奶牛之间都有一条唯一的通路。FJ 希望 Bessie 尽快的回到农场。于是他就指示 Bessie如果对于一条路直接相连的两个奶牛Bessie 只能拜访其中的一个。当然Bessie 希望她的假期越长越好所以她想知道她可以拜访的奶牛的最大数目。【输入】第一行1 11个整数N NN。接下来N − 1 N - 1N−1行每行2 22个整数C 1 , C 2 C_1,C_2C1​,C2​表示有一条通路连接了编号为C 1 C_1C1​和C 2 C_2C2​的奶牛。【输出】第一行1 11个整数代表 Bessie 最多能拜访有多少头奶牛。【输入样例】7 6 2 3 4 2 3 1 2 7 6 5 6【输出样例】4【核心思想】问题分析给定N NN个节点的树要求选择尽可能多的节点使得任意两个被选节点之间没有直接相连的边即独立集。这是一个经典的树形 DP问题核心在于每个节点只有选或不选两种状态且相邻节点不能同时选。算法选择树形 DPf [ u ] [ 0 / 1 ] f[u][0/1]f[u][0/1]表示以u uu为根的子树中u uu不选0 00或选1 11时的最大独立集大小DFS 遍历从根节点出发递归处理每个子树关键步骤初始化读取N NN和N − 1 N-1N−1条边建立无向邻接表找根节点无父节点的节点DFS 状态转移节点u uu父节点f a fafaf [ u ] [ 1 ] 1 f[u][1] 1f[u][1]1选u uu至少包含u uu自己遍历u uu的所有邻接节点v vv跳过父节点f a fafa递归d f s ( v , u ) dfs(v, u)dfs(v,u)f [ u ] [ 0 ] max ⁡ ( f [ v ] [ 0 ] , f [ v ] [ 1 ] ) f[u][0] \max(f[v][0], f[v][1])f[u][0]max(f[v][0],f[v][1])u uu不选v vv可选可不选取较大值f [ u ] [ 1 ] f [ v ] [ 0 ] f[u][1] f[v][0]f[u][1]f[v][0]u uu选v vv不能选输出答案max ⁡ ( f [ r o o t ] [ 0 ] , f [ r o o t ] [ 1 ] ) \max(f[root][0], f[root][1])max(f[root][0],f[root][1])时间/空间复杂度时间复杂度O ( N ) O(N)O(N)每个节点访问一次每条边处理一次空间复杂度O ( N ) O(N)O(N)邻接表和 DP 数组树形 DP 的核心思想状态设计每个节点只有两种状态子问题相互独立子树之间互不影响父子约束选父节点则不能选子节点不选父节点则子节点可选可不选后序遍历先递归处理所有子节点再处理当前节点确保子树状态已计算完毕最优子结构以u uu为根的子树的最优解仅依赖于各子树的最优解适用于树的最大独立集、树的最小点覆盖、树的最小支配集类问题【算法标签】#普及 #树形DP【代码详解】#includebits/stdc.husingnamespacestd;constintN50005;// 最大奶牛数量intn;// n:奶牛数量也是树的节点数vectorintg[N];// g[u]:节点u的邻接表intf[N][2];// f[u][0/1]:以u为根的子树中u不选(0)/选(1)时的最大拜访数boolst[N];// st[i]:标记节点i是否有父节点用于找根// 树形DPdfs遍历整棵树voiddfs(intu,intfa)// u:当前节点, fa:父节点{f[u][1]1;// 如果选u至少可以拜访u自己for(inti0;ig[u].size();i)// 遍历u的所有子节点{intvg[u][i];// v:u的邻接节点if(vfa)continue;// 跳过父节点避免回溯dfs(v,u);// 递归处理子树// 状态转移u不选时子节点v可选可不选取较大值f[u][0]max(f[v][0],f[v][1]);// 状态转移u选时子节点v不能选相邻不能同时选f[u][1]f[v][0];}}intmain(){cinn;// 读入奶牛数量for(inti1;in;i)// 读入n-1条边{intc1,c2;cinc1c2;g[c1].push_back(c2);// 无向图双向建边g[c2].push_back(c1);st[c2]true;// 标记c2有父节点c1是c2的父节点之一}// 找树的根节点没有父节点的节点introot1;for(inti1;in;i)if(!st[i])// 如果节点i没有父节点{rooti;break;}dfs(root,0);// 从根节点开始DFS// 答案根节点选或不选的最大值coutmax(f[root][0],f[root][1])endl;return0;}【运行结果】7 6 2 3 4 2 3 1 2 7 6 5 6 4