毛毛虫
题目描述
对于一棵树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫，点数越多，毛毛虫就越大。例如下图左边的树（图 1）抽出一部分就变成了右边的一个毛毛虫了（图 2）。
输入格式
输入中第一行两个整数 N,M，分别表示树中结点个数和树的边数。
接下来 M 行，每行两个整数 a,b 表示点 a 和点 b 有边连接（a,b≤N）。你可以假定没有一对相同的 (a,b) 会出现一次以上。
输出格式
输出一行一个整数 , 表示最大的毛毛虫的大小。
分析and代码：
数据结构的定义和变量的定义
const int N = 300009;
vector<int> e[N];int f[N], ans;
- N：定义了节点数量的上限。
- e[N]：使用邻接表存储树的结构，e[u] 存储与节点 u 相邻的所有节点。
- f[N]：f[u] 表示以节点 u 为根的子树中，包含节点 u 且向子树方向延伸的最长 “毛毛虫” 分支的节点数。
- ans：用于记录全局最大的 “毛毛虫” 大小。
dfs函数
void dfs(int u, int fa) {
int mx0 = 0, mx1 = 0; // 最大，次大
for (int i = 0, v; i < e[u].size(); i++)
if ((v = e[u][i]) != fa) {
dfs(v, u); // 先处理子节点
f[u] = max(f[u], f[v]); // f更新
if (f[v] > mx0) mx1 = mx0, mx0 = f[v];
else if (f[v] > mx1) mx1 = f[v];
}
int cnt = e[u].size() - (fa != -1);
f[u] += (1 + max(0, cnt - 1));
ans = max(ans, mx0 + mx1 + 1 + max(0, cnt - 1 - (fa == -1)));}
- 初始化：mx0 和 mx1 分别用于记录以 u 的子节点为根的子树中最长和次长的 “毛毛虫” 分支的节点数。
- 递归处理子节点：遍历 u 的所有邻接节点 v，如果 v 不是 u 的父节点 fa，则递归调用 dfs(v, u) 处理子节点。
- 更新 f[u]：f[u] 取 f[u] 和 f[v] 中的最大值，确保 f[u] 记录的是最长的 “毛毛虫” 分支。
- 更新 mx0 和 mx1：如果 f[v] 大于 mx0，则更新 mx1 为原来的 mx0，mx0 为 f[v]；如果 f[v] 大于 mx1 但小于 mx0，则更新 mx1 为 f[v]。
- 计算与 u 相连的边数：cnt 表示与节点 u 相连且不是其父节点的边的数量。
- 更新 f[u]：f[u] 加上 1 + max(0, cnt - 1)，这里的 1 表示节点 u 自身，max(0, cnt - 1) 表示除了最长分支外，与 u 相连的其他边所贡献的节点数。
- 更新最大 “毛毛虫” 大小：ans 取 ans 和 mx0 + mx1 + 1 + max(0, cnt - 1 - (fa == -1)) 中的最大值，其中 mx0 + mx1 表示最长和次长分支的节点数，1 表示节点 u 自身，max(0, cnt - 1 - (fa == -1)) 表示除了这两个分支外，与 u 相连的其他边所贡献的节点数。
主函数
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i <= m; i++)
scanf("%d%d", &u, &v), e[u].push_back(v), e[v].push_back(u);
dfs(1, -1);
printf("%d", ans);
return 0;}
- 读取输入：读取树的节点数 n 和边数 m，并依次读取每条边的两个端点 u 和 v，将其添加到邻接表中。
- 深度优先搜索：从节点 1 开始进行深度优先搜索，初始父节点设为 -1。
- 输出结果：输出最大的 “毛毛虫” 大小 ans。
题目描述
The king of Byteotia, Byteasar, is returning to his country after a victorious battle.
In Byteotia, there are towns connected with only roads.
It is known that every town can be reached from every other town by a unique route, consisting of one or more (direct) roads.
(In other words, the road network forms a tree).
The king has just entered the capital.
Therein a triumphal arch, i.e., a gate a victorious king rides through, has been erected.
Byteasar, delighted by a warm welcome by his subjects, has planned a triumphal procession to visit all the towns of Byteotia, starting with the capital he is currently in.
The other towns are not ready to greet their king just yet - the constructions of the triumphal arches in those towns did not even begin!
But Byteasar's trusted advisor is seeing to the issue.
He desires to hire a number of construction crews.
Every crew can construct a single arch each day, in any town.
Unfortunately, no one knows the order in which the king will visit the towns.
The only thing that is clear is that every day the king will travel from the city he is currently in to a neighboring one.
The king may visit any town an arbitrary number of times (but as he is not vain, one arch in each town will suffice).
Byteasar's advisor has to pay each crew the same flat fee, regardless of how many arches this crew builds.
Thus, while he needs to ensure that every town has an arch when it is visited by the king, he wants to hire as few crews as possible.
Help him out by writing a program that will determine the minimum number of crews that allow a timely delivery of the arches.
给一颗 n 个节点的树（n≤3×105），初始时 1 号节点被染黑，其余是白的。两个人轮流操作，一开始 B 在 1 号节点。每一轮，A 选择 k 个点染黑，然后 B 走到一个相邻节点，如果 B 当前处于白点则 B 胜，否则当 A 将所有点染为黑点时 A 胜。求能让 A 获胜的最小的 k 。
输入格式
The first line of the standard input contains a single integer
(), the number of towns in Byteotia.
The towns are numbered from 1 to , where the number 1 corresponds to the capital.
The road network is described in lines that then follow.
Each of those lines contains two integers。 separated by a single space, indicating that towns
and are directly connected with a two way road.
In tests worth 50% of the total points, an additional condition holds.
输出格式
The first and only line of the standard output is to hold a single integer, the minimum number of crews that Byteasar's advisor needs to hire.
分析
1. 树的构建
- 读取输入的节点数量 n 和 n - 1 条边的信息。
- 利用这些边的信息构建树的邻接表，以此来表示树的结构，方便后续对树进行遍历操作。
2. 计算子节点数量
- 运用深度优先搜索（DFS）算法，从根节点（节点 1）开始遍历整棵树。
- 在遍历过程中，对于每个节点，统计其直接相连的子节点数量，并将结果记录下来。
3. 二分查找最小的 k 值
- 确定二分查找的左右边界：左边界 l 初始化为根节点的子节点数量，右边界 r 初始化为所有节点子节点数量的最大值。
- 进入二分查找的循环，不断取中间值 mid 作为当前尝试的 k 值。
- 对于每个 mid 值，使用动态规划（DP）计算在该 k 值下根节点的有效子节点数量。
- 根据根节点有效子节点数量的计算结果调整二分查找的区间：
- 若根节点的有效子节点数量不超过 0，说明当前 k 值满足条件，将右边界更新为 mid - 1，并记录当前 mid 为可能的答案。
- 若根节点的有效子节点数量大于 0，说明当前 k 值太小，将左边界更新为 mid + 1。
4. 动态规划计算有效子节点数量
- 对于树中的每个节点，先将其有效子节点数量初始化为该节点的子节点数量减去当前的 k 值。
- 遍历该节点的所有子节点，若子节点的有效子节点数量大于 0，则将其累加到当前节点的有效子节点数量中。
- 通过递归的方式对树中的所有节点进行上述操作，最终得到根节点的有效子节点数量。
5. 输出结果
- 当二分查找结束后，记录的答案即为满足条件的最小 k 值，将其输出。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=300010;
unordered_map<int,vector<int>> e;
int son[N];
int f[N];
int n;
void dfs(int u,int fa){
for(int v:e[u]){
if(v==fa)continue;
son[u]++;
dfs(v,u);
}
}void dp(int u,int fa,int k){
f[u]=son[u]-k;
for(int v:e[u]){
if(v==fa)continue;
dp(v,u,k);
if(f[v]>0)f[u]+=f[v];
}
}int main(){
cin>>n;
for(int i=0;i<n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,-1);
int l=son[1],r=l;
int ans=0;
for(int i=1;i<=n;i++)r=max(r,son[i]);
while(l<=r){
int mid=l+r>>1;
dp(1,0,mid);
if(f[1]<=0){
r=mid-1;
ans=mid;
}else l=mid+1;
}
cout<<ans;
}
)
