CodeForces - 686D Kay and Snowflake(求一棵树的每颗子树的重心)

分析:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1000052;
vector <int> u[maxn];
int n, m, ans[maxn], s[maxn], fa[maxn];
void dfs(int x, int fas) {
	s[x] = 1;
	fa[x] = fas;
	int max_son = -1;
	for (int i = 0; i < u[x].size(); i++) {
		if (u[x][i] == fas) continue;
		dfs(u[x][i], x);
		s[x] += s[u[x][i]];
		if (max_son == -1 || s[u[x][i]] > s[max_son]) {
			max_son = u[x][i];
		}
	}
	if (max_son == -1) {
		ans[x] = x;
	}
	else {
		max_son = ans[max_son];
		while (2 * s[max_son] < s[x] ) {
			max_son = fa[max_son];
		}
		ans[x] = max_son;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 2; i <= n; i++) {
		int temp;
		cin >> temp;
		u[temp].push_back(i);
		u[i].push_back(temp);
	}
	dfs(1,-1);
	while (m--) {
		int pos;
		cin >> pos;
		cout << ans[pos] << endl;
	}
}
全部评论

相关推荐

珩珺:那些经历都太大太空了,实习的情况不了解,大创项目连名字、背景、目的及意义都没体现出来;地摊经济更是看完连卖的什么产品都不知道,项目成果直接写营收多少都更直观真实一点;后面那个校文体部的更是工作内容是组织活动整理流程,成果变成了当志愿者,而且你们学校本科学生会大一入学就直接当部长吗,志愿里面还提到了疫情防控,全面解封是22年12月的事情,可能时间上也有冲突。可能你花了钱人家就用AI给你随便写了点内容改了一下,没什么体现个性化的点
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务