1.题目描述
魔法王国一共有 n 个城市,编号为 0~n-1 号,n 个城市之间的道路连接起来恰好构成一棵树。小易现在在 0 号城市,每次行动小易会从当前所在的城市走到与其相邻的一个城市,小易最多能行动 L 次。
如果小易到达过某个城市就视为小易游历过这个城市了,小易现在要制定好的旅游计划使他能游历最多的城市,请你帮他计算一下他最多能游历过多少个城市(注意 0 号城市已经游历了,游历过的城市不重复计算)。
- 输入描述:
输入包括两行,
第一行包括两个正整数 n(2 ≤ n ≤ 50)和 L(1 ≤ L ≤ 100),表示城市个数和小易能行动的次数。
第二行包括 n-1 个整数 parent[i](0 ≤ parent[i] ≤ i), 对于每个合法的 i(0 ≤ i ≤ n - 2),在(i+1)号城市和 parent[i]间有一条道路连接。 - 输出描述:
输出一个整数,表示小易最多能游历的城市数量。 - 输入例子 1:
5 2 0 1 2 3 - 输出例子 1:
3
2.题目解析
题目给出的示例
因为城市连接是一棵树，所以可能是这样
也可能是这样
所以，问题变成树的遍历。从0开始出发，记录到每个节点的长度。
然后，判断L与最长路线(经过城市最多路线)的城市数量max_num比较(注意：步数比经过城市数少1)。
如果L < max_num -1，那么只能访问max_num个城市。
如果L > max_num -1，那么分两种情况。
-
L足够大，游历了所有城市。 -
L一般大，只游历了部分城市和最长路线(经过城市最多路线)上的城市。
这两种请况，为了行动次数最少，先游历其他城市，最后游历最长路线(经过城市最多路线)上的城市。这样其他城市每次游历需要行动两次(一个来回，从最长路线出发，然后回到最长路线)。
L足够大，游历所有城市至少需要行动多少次？(n - max_num)*2+max_num
L一般大，能够游历多少个城市？(L-max_num)/2+max_num
3.参考答案
#include <bits/stdc++.h>
using namespace std;
int main(){
int n = 0;
int L = 0;
scanf("%d%d",&n,&L);
int parent[n-1];
for(int i=0;i<n-1;++i){
scanf("%d",&parent[i]);
}
// 计算最长路径的长度
int dist[n-1];// 记录每个节点到根节点的长度
dist[0] = 0;
int max_len = 0;
for(int i=0;i<n-1;++i){
int now = i+1; // 当前节点下标
int prev = parent[i]; // 父节点下标
dist[now] = dist[prev] + 1; // 当前节点与根节点的距离 = 父节点与根节点的距离 + 1
max_len = max(max_len,dist[now]);// 记录最长距离
}
// printf("%d",max_len);
int citys = 0;
// L一般大只能访问最长路径上的城市
if(L <= max_len){ // 只能访问最长路径上的城市
citys = L+1;
// L足够大可以访问所有的城市
}else if(L >= (n-max_len-1)*2 + max_len){// max_len最长路径行动数，(n-max_len-1)*2是其他节点需要往返访问的行动数
citys = n;
// L介于两者之间，能访问最长路径上的城市，或许能多访问其他路径上的城市
}else{
citys = max_len+1+(L-max_len)/2;
}
printf("%d\n",citys);
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; // 城市个数
int L; // 小易能行动的次数
scanf("%d%d", &n, &L);
// 在(i+1)号城市和parent[i]间有一条道路连接。
int parent[n-1];
for(int i = 0; i < n - 1; ++i)
scanf("%d", &parent[i]);
int dp[n]; // 表示从0到i节点需要经过几个城市
dp[0] = 1; // 编号0城市算作游历城市
int max_num = 0; // 最大值经过的城市数
for(int i = 0; i < n - 1; ++i) {
// 到达城市i+1，是到达城市i经过的数目再加上1
dp[i + 1] = dp[parent[i]] + 1;
max_num = max(max_num, dp[i + 1]);
}
// 获取步数最少的值。
if (L <= max_num-1) { // 走到中途停止
printf("%d\n",L+1);
} else {
// 可以多游历的城市
int leave = (L-max_num +1)/2;// 除2表示每次都要走一个来回
if (L >= (n-max_num)*2+max_num) {// L足够大的情况
printf("%d\n",n);
} else { // L一般大的情况
printf("%d\n",max_num+leave);
}
}
return 0;
}
