链接:https://ac.nowcoder.com/acm/contest/9045/F 来源:牛客网
DLB是村里的勇者,他一直保卫着村庄的和平,以不受野兽的侵扰。而野兽们也对DLB恨之入骨,于是野兽们决定组织一次集体进攻,打败DLB,占领村庄。
DLB知道,野兽集体进攻的时候,会在彼此之间建立一种链接,而被这种链接关联起来的野兽能够增长彼此的攻击力,且每有一只野兽加入到一个链接中,这个链接里的所有野兽的攻击力都会加1,而只有当DLB的战力大于野兽的攻击力时,才能将野兽杀死。万幸的是,DLB有一把无敌的宝剑,他可以秒杀掉一只野兽,并消除这条野兽身上的所有链接,但这把宝剑只能使用一次。
假设每条野兽不被关联时的攻击力为1,初始时所有N只野兽被N-1条链接关联在一起。DLB想知道他至少要有多少的战力,才能将所有野兽都杀死,同时他想知道,他应该用宝剑杀掉哪只野兽。
输入的第一行是一个整数N(1<N<=50), 表示一共有N只野兽。
接下来N-1行整数对a,b(以空格分隔),表示野兽之间的链接关系
xxxxxxxxxx
输出两个整数。
第一个整数X,表示应用宝剑杀死野兽的编号。若有多只野兽都可被宝剑杀死,输出编号最小的那个 第二个整数T,表示DLB至少需要有的战斗力
示例1
xxxxxxxxxx
8
1 2
2 3
1 5
5 6
6 8
2 4
5 7
xxxxxxxxxx
1 5
xxxxxxxxxx
初始时所有野兽都在一个链接中,此时所有野兽的战斗力都为8。
当用宝剑杀死1号野兽后,剩下的野兽分别在两个链接中(2,3,4和5,6,7,8),此时5,6,7,8号野兽战斗力皆为4;2,3,4号野兽的战斗力为3。
故DLB的战斗力至少为5才可杀死所有野兽。
x
using namespace std;
const int N = 51;
const int M = N << 1;
int head[N], to[M], nex[M], cnt_edge;
int ind, max_z = N; // ind记录数的重心编号,max_z记录以ind为根节点的最大子树的节点数量
int n;
void add(const int &a, const int &b) {
to[++cnt_edge] = b;
nex[cnt_edge] = head[a];
head[a] = cnt_edge;
return ;
}
bool vis[N];
int dfs(const int &u) {//以u为根节点计算这棵树的节点数量包括u
int sum = 1; //记录节点数量
vis[u] = true; //标记
int ret = 0; //统计以u为根节点的子树的最大节点数量
for (int i = head[u]; i; i = nex[i]) {
if (!vis[to[i]]) {
int s = dfs(to[i]);
ret = max(ret, s);
sum += s;
}
}
// cout << u << ": " << sum << endl;
ret = max(n - sum, ret); //向上比较
if (ret < max_z) {
// cout << ind << " " << max_z + 1 << endl;
ind = u;
max_z = ret;
} else if (ret == max_z && ind > u) ind = u; //获取id编号小的节点
return sum;
}
int main() {
cin >> n;
for (int i = 1, a, b; i < n; ++i) {
cin >> a >> b;
add(a, b);
add(b, a);
}
dfs(1); //以1为根节点计算这棵树的节点数量包括自己
cout << ind << " " << max_z + 1 << endl;
return 0;
}