企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、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

【核心思想】

1. 问题分析：给定N NN个节点的树，要求选择尽可能多的节点，使得任意两个被选节点之间没有直接相连的边（即独立集）。这是一个经典的树形 DP问题，核心在于每个节点只有"选"或"不选"两种状态，且相邻节点不能同时选。

2. 算法选择：

   • 树形 DP：f [ u ] [ 0 / 1 ] f[u][0/1]f[u][0/1]表示以u uu为根的子树中，u uu不选（0 00）或选（1 11）时的最大独立集大小
   • DFS 遍历：从根节点出发，递归处理每个子树

3. 关键步骤：

   • 初始化：读取N NN和N − 1 N-1N−1条边，建立无向邻接表，找根节点（无父节点的节点）
   • DFS 状态转移（节点u uu，父节点f a fafa）：
     • f [ 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])

4. 时间/空间复杂度：

   • 时间复杂度：O ( N ) O(N)O(N)，每个节点访问一次，每条边处理一次
   • 空间复杂度：O ( N ) O(N)O(N)，邻接表和 DP 数组

5. 树形 DP 的核心思想：

   • 状态设计：每个节点只有两种状态，子问题相互独立（子树之间互不影响）
   • 父子约束：选父节点则不能选子节点，不选父节点则子节点可选可不选
   • 后序遍历：先递归处理所有子节点，再处理当前节点，确保子树状态已计算完毕
   • 最优子结构：以u uu为根的子树的最优解仅依赖于各子树的最优解
   • 适用于树的最大独立集、树的最小点覆盖、树的最小支配集类问题

【算法标签】

#普及 #树形DP

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=50005;// 最大奶牛数量intn;// n:奶牛数量（也是树的节点数）vector<int>g[N];// g[u]:节点u的邻接表intf[N][2];// f[u][0/1]:以u为根的子树中，u不选(0)/选(1)时的最大拜访数boolst[N];// st[i]:标记节点i是否有父节点（用于找根）// 树形DP：dfs遍历整棵树voiddfs(intu,intfa)// u:当前节点, fa:父节点{f[u][1]=1;// 如果选u，至少可以拜访u自己for(inti=0;i<g[u].size();i++)// 遍历u的所有子节点{intv=g[u][i];// v:u的邻接节点if(v==fa)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(){cin>>n;// 读入奶牛数量for(inti=1;i<n;i++)// 读入n-1条边{intc1,c2;cin>>c1>>c2;g[c1].push_back(c2);// 无向图，双向建边g[c2].push_back(c1);st[c2]=true;// 标记c2有父节点（c1是c2的父节点之一）}// 找树的根节点：没有父节点的节点introot=1;for(inti=1;i<=n;i++)if(!st[i])// 如果节点i没有父节点{root=i;break;}dfs(root,0);// 从根节点开始DFS// 答案：根节点选或不选的最大值cout<<max(f[root][0],f[root][1])<<endl;return0;}

【运行结果】

7 6 2 3 4 2 3 1 2 7 6 5 6 4