3501. Message transmission

Description

State H has a strict social hierarchy. Apart from the king, each person has and has only one direct superior. Of course, the king has no superior. If a is superior to B and B is superior to C, then a is superior to C. There will never be such a relationship: A is the superior of B, and B is also the superior of A.

The first time is 0. What you have to do is to use 1 unit time to tell a message to someone and let them spread the message by themselves. In any time unit, anyone who has received a message can tell the message to one of his direct superiors or direct subordinates.

Now, you want to know:

1. How long will it take for the news to reach all the people in H country?

2. What are the people that can be selected to minimize the time consumed in message delivery?

Input

The first line of the input file is an integer n (n ≤ 200000), which represents the total number of H people. If people are numbered according to 1 to N, the king's number is 1.

From line 2 to line N (N-1 in total), each line is an integer, and the integer in line i represents the number of the direct superior of the person whose number is i.

Output

There are two lines of output:

The first line is an integer indicating the earliest time the last person received the message.

There are several numbers in the second line, indicating the number of optional persons. The number is output from small to large, separated by a space.

Sample Input

Input 1:

4
1
1
1

Input 2:

8
1
1
3
4
4
4
3

Sample Output

Output 1:

4
1 2 3 4

Output 2:

5
3 4 5 6 7

Data Constraint

For 20% of the data, meet n < = 3000;

For 50% data, n < = 20000;

For 100% data, n < = 200000;

Solution

Tree dp.

Let f[i] represent the minimum time after processing the subtree with I as the root,rank[j] means that the f value of j is the lowest among all the sons of i.

Then consider changing the root dp, let g[i] represent the answer of the whole tree with the father of I as the root after removing the subtree of I.

So when we change the root, we sort the g value of I and the f value of all our sons together to get the rank array, and then we can use the above formula to find the answer with I as the root after changing the root. The final question is how to find g, because g[i] must have been found when finding the answer of I, so we should find out the g value of each son from I, then we will sort all sons and their own g values, and consider deleting the middle answer after X, then the rank of the number before X does not change at this time, while the rank of the number after X is - 1, so we preprocess a prefix Max and suffix Max represent the minimum value of f[j]+rank[j] in the first I (or last I) number, then the g value of j can be transferred from max(pre[x-1],suf[x+1]-1).

Code

#include<cstdio> 
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(register I i=a;i<=b;++i)
#define Fd(i,a,b) for(register I i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof a)
#define N 200005
using namespace std;
I n,x,t[N<<1],nx[N<<1],l[N],suf[N],pre[N],f[N],tot,ans[N],answer,g[N];
struct SON{I x,v;}s[N];
void rd(I &x){
	x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
}
void A(I x,I y){t[++tot]=y,nx[tot]=l[x],l[x]=tot;}
I cmp(SON x,SON y){return x.v>y.v;}
I cmp2(I x,I y){return x<y;}
void dg(I x,I y){
	for(I k=l[x];k;k=nx[k]) if(y!=t[k]) dg(t[k],x);
	tot=0;
	for(I k=l[x];k;k=nx[k]) if(y!=t[k]){s[++tot]=SON{t[k],f[t[k]]};}
	sort(s+1,s+1+tot,cmp);
	F(i,1,tot) f[x]=max(f[x],s[i].v+i);
}
void getans(I x,I y){
	tot=0;
	if(x!=1) s[++tot]=SON{-1,g[x]};
	for(I k=l[x];k;k=nx[k]) if(t[k]!=y) s[++tot]=SON{t[k],f[t[k]]};
	sort(s+1,s+1+tot,cmp);
	pre[0]=suf[tot+1]=0;
	F(i,1,tot) pre[i]=max(pre[i-1],s[i].v+i);
	Fd(i,tot,1) suf[i]=max(suf[i+1],s[i].v+i-1);
	F(i,1,tot) if(s[i].x>0) g[s[i].x]=max(pre[i-1],suf[i+1]);
	if(answer>pre[tot]){answer=pre[tot],ans[0]=0;}
	if(answer==pre[tot]) ans[++ans[0]]=x;
	for(I k=l[x];k;k=nx[k]) if(y!=t[k]) getans(t[k],x);
}
I main(){
	freopen("news.in","r",stdin);
	freopen("news.out","w",stdout);
	rd(n);
	F(i,2,n){rd(x);A(x,i);A(i,x);}
	dg(1,0);
	answer=N+1;
	getans(1,0);
	sort(ans+1,ans+1+ans[0],cmp2);
	printf("%d\n",answer+1);
	F(i,1,ans[0]) printf("%d ",ans[i]);
	return 0;
}

 

Published 201 original articles, praised 204, visited 20000+
Private letter follow

Posted on Thu, 06 Feb 2020 03:28:31 -0800 by Dan_Mason