消息传递(news)题解

代码

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 200000;

int f[N + 5] , g[N + 5] , h[N + 5] , son[N + 5] , res[N + 5] , Maxl[N + 5] , Maxr[N + 5];

int tot = 1 , cnt , n , F , ans;

struct edge{

	int to , nxt;

}e[N + 5];

inline void add(int x , int y) {e[++tot].to = y , e[tot].nxt = h[x] , h[x] = tot;}

inline int o(int x){return x == F ? g[x] : f[x];}

inline bool cmp(int x , int y) {return o(x) > o(y);}

inline void getf(int u)

{

	for(register int i = h[u]; i; i = e[i].nxt) getf(e[i].to);

	cnt = F = 0;

	for(register int i = h[u]; i; i = e[i].nxt) son[++cnt] = e[i].to;

	sort(son + 1 , son + cnt + 1 , cmp);

	for(register int i = 1; i <= cnt; i++) f[u] = max(f[u] , f[son[i]] + i);

}

inline void getg(int u)

{

	if (u > 1) son[cnt = 1] = F = u;

	else cnt = F = 0;

	for(register int i = h[u]; i; i = e[i].nxt) son[++cnt] = e[i].to;

	sort(son + 1 , son + cnt + 1 , cmp);

	Maxl[0] = Maxr[cnt + 1] = 0;

	for(register int i = 1; i <= cnt; i++) Maxl[i] = max(Maxl[i - 1] , o(son[i]) + i);

	for(register int i = cnt; i >= 1; i--) Maxr[i] = max(Maxr[i + 1] , o(son[i]) + i);

	for(register int i = 1; i <= cnt; i++)

	{

		if (son[i] == u) continue;

		g[son[i]] = max(Maxl[i - 1] , Maxr[i + 1] - 1);

	}

	res[u] = Maxl[cnt];

	for(register int i = h[u]; i; i = e[i].nxt) getg(e[i].to);

}

inline int read()

{

	char ch = getchar();

	int x = 0;

	for(; ch < '0' || ch > '9'; ch = getchar());

	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';

	return x;

}

int main()

{

	freopen("news.in" , "r" , stdin);

	freopen("news.out" , "w" , stdout);

	n = read();

	int fa;

	for(register int i = 2; i <= n; i++) fa = read() , add(fa , i);

	getf(1) , getg(1);

	ans = 2e9;

	for(register int i = 1; i <= n; i++) ans = min(res[i] , ans);

	printf("%d\n" , ans + 1);

	for(register int i = 1; i <= n; i++)

	if (res[i] == ans) printf("%d " , i);

}
巴特西

消息传递(news)题解

代码

最新文章

热门文章
