1773：消息传递
时间限制: 1000 ms 内存限制: 262144 KB
【题目描述】
H国的社会等级森严，除了国王之外，每个人均有且只有一个直接上级，当然国王没有上级。如果A是B的上级，B是C的上级，那么A就是C的上级。绝对不会出现这样的关系：A是B的上级，B也是A的上级。
最开始的时刻是0，你要做的就是用1单位的时间把一个消息告诉某一个人，让他们自行散布消息。在任意一个时间单位中，任何一个已经接到消息的人，都可以把消息告诉他的一个直接上级或者直接下属。
现在，你想知道：
①到底需要多长时间，消息才能传遍整个H国的所有人？
②要使消息在传递过程中消耗的时间最短，可供选择的人有哪些？
【输入】
第一行为一个整数N，表示H国人的总数，假如人按照1到n编上了号码，国王的编号是1。
第二行到第N行（共N−1行），每一行一个整数，第i行的整数表示编号为i的人直接上级的编号。
【输出】
输出共计两行：
第一行为一个整数，表示最后一个人接到消息的最早时间。
第二行有若干个数，表示可供选择人的编号，按照编号从小到大的顺序输出，中间用一个空格隔开。
【输入样例】
4
1
1
1
【输出样例】
4
1 2 3 4
【输入样例2】
8
1
1
3
4
4
4
3
【输出样例2】
5
3 4 5 6 7
【数据规模与约定】
对于20%的数据，N≤3000。
对于50%的数据，N≤20000。
对于100%的数据，N≤200000。
【题解】
实际上是一道水题。
可以很方便的求出以u为根传递完它的子树的代价f[u]。
考虑如何求出传完它父亲及其上方点的代价。
使用换根dp。令g[u]表示去掉u及其子树并以u的父亲为根的全部代价。
将所有儿子的f与自己的g排序后即可求出所有儿子的g。
每个点的答案就很好计算了。
代码如下：
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int f[N],g[N],n,last[N],size,pre[N],sub[N],ans[N],ans1=999999999,daan[N],ans2; struct pigu { int dao,ne; }a[N]; pair <int,int> b[N]; inline void lingjiebiao(int x,int y) { a[++size].dao=y; a[size].ne=last[x]; last[x]=size; } inline void dfs1(int now) { for(int i=last[now];i;i=a[i].ne) dfs1(a[i].dao); int cnt=0; for(int i=last[now];i;i=a[i].ne) b[++cnt]=make_pair(f[a[i].dao],a[i].dao); sort(b+1,b+cnt+1); for(int i=1;i<=cnt;i++) f[now]=max(f[now],b[i].first+cnt-i+1); } inline void dfs2(int now) { int cnt=0; for(int i=last[now];i;i=a[i].ne) { b[++cnt]=make_pair(f[a[i].dao],a[i].dao); } if(now!=1) b[++cnt]=make_pair(g[now],-1); if(cnt==1&&now==1) g[now]=1; sort(b+1,b+cnt+1); for(int i=1;i<=cnt;i++) ans[now]=max(b[i].first+cnt-i+1,ans[now]);pre[0]=sub[cnt+1]=-1; for(int i=1;i<=cnt;i++) pre[i]=max(pre[i-1],b[i].first+cnt-i); for(int i=cnt;i>=2;i--) sub[i]=max(sub[i+1],b[i].first+cnt-i+1); for(int i=1;i<=cnt;i++) { if(b[i].second!=-1) g[b[i].second]=max(pre[i-1],sub[i+1]); } for(int i=last[now];i;i=a[i].ne) dfs2(a[i].dao); } int main() { scanf("%d",&n); for(int i=2,x;i<=n;i++) { scanf("%d",&x); lingjiebiao(x,i); } dfs1(1); dfs2(1); for(int i=1;i<=n;i++) if(ans1>ans[i]) ans1=ans[i],daan[ans2=1]=i; else if(ans1==ans[i]) daan[++ans2]=i; cout<<ans1+1<<" "; for(int i=1;i<=ans2;i++) cout<<daan[i]<<" "; return 0; }