方法大概就是枚举每一个投放病毒的点,然后以它为根建树,这样病毒每次必定只能向下传递,用f[i]表示把以i为根的子树的时间 那么转移为 f[i]=max(f[son[i][1]]+val1,f[son[i][2]]+val2......)
显然将f[son[i]]从小到大排序,使最大的加上1,最小的加上k(k为儿子数).....即可

#include<bits/stdc++.h>
using namespace std;
const int N=1000+10;
int f[N],last[N],n,len=0;
struct Edge{int to,next;Edge(int to=0,int next=0):to(to),next(next){}}e[N<<1];
void add_edge(int u,int v){e[++len]=Edge(v,last[u]);last[u]=len;}
int dfs(int x,int fa)
{
    int top=0,s[N],tot=0;
    for(int i=last[x];i;i=e[i].next)
    {
        int id=e[i].to;
        if(id==fa)continue;
        s[++top]=dfs(id,x);
    }
    if(top==0){return 0;}
    sort(s+1,s+1+top);
    for(int i=1;i<=top;i++)
        tot=max(tot,s[i]+top+1-i);
    return tot;
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int u;scanf("%d",&u);
        add_edge(i,u);add_edge(u,i);
    }
    int mn=0x7ffffff;
    for(int i=1;i<=n;i++) {f[i]=dfs(i,0); mn=min(mn,f[i]);}
    printf("%d\n",mn+1);
    for(int i=1;i<=n;i++) 
        if(f[i]==mn) printf("%d ",i);
    cout<<endl;
    return 0;
}

看了下别人讨论的题解才想到的，不过方法和他的不同，

首先N只有1000， 如果能做到暴力枚举每一个节点，然后O（N）算出其贡献，那么也在允许的时间内。

假设我们现在对1这个节点进行计数，设dp[i]表示入侵i号节点和其所有子树所需要的最小时间。

那么、假设1号有k个儿子，dp[son1] 、 dp[son2]、 dp[sonk]都算出来了，那么dp[1] = max(dp[son])对吧。

但是入侵这些儿子都有一定的规矩，就是每一秒只能入侵一个，那么总是有一些儿子是最后才入侵的，就是要隔k秒后（最坏情况）才入侵这个儿子，

所以把所有儿子的权值排序，要使得max值最小，那么dp[son]值最小的，我们最后才入侵

dp[son1] += k

dp[son2] += k - 1

dp[son3] += k - 2

......

这样是最优的。

然后这一个过程时间是O(nlogn)

也能接受。

注意的是输出的时候id要按小到大输出，不然wa9

#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e3 + 20;
struct Edge {
    int u, v, tonext;
}e[maxn * 2];
int first[maxn], num;
void addEdge(int u, int v) {
    ++num;
    e[num].u = u, e[num].v = v, e[num].tonext = first[u];
    first[u] = num;
}
int dp[maxn];
vector<int>vc[maxn];
int dfs(int cur, int fa) {
    int son = 0;
    vc[cur].clear();
    for (int i = first[cur]; i; i = e[i].tonext) {
        int v = e[i].v;
        if (fa == v) continue;
        son++;
        vc[cur].push_back(dfs(v, cur));
    }
    if (vc[cur].size() == 0) return 0;
    sort(vc[cur].begin(), vc[cur].end());
    for (int i = 0; i < vc[cur].size(); ++i) {
        vc[cur][i] += son;
        son--;
    }
    sort(vc[cur].begin(), vc[cur].end());
    return vc[cur].back();
}
struct Node {
    int val, id;
    Node(int _val, int _id) {
        val = _val, id = _id;
    }
    bool operator < (const struct Node & rhs) const {
        if (val != rhs.val) return val < rhs.val;
        else return id < rhs.id;
    }
};
vector<struct Node>res;
void work() {
    num = 0;
    memset(first, 0, sizeof first);
    int n;
    scanf("%d", &n);
    int root = 1;
    for (int i = 2; i <= n; ++i) {
        int fa;
        scanf("%d", &fa);
        addEdge(fa, i);
        addEdge(i, fa);
    }
    for (int i = 1; i <= n; ++i) {
        res.push_back(Node(dfs(i, 0) + 1, i));
    }
//    for (int i = 0; i <= n - 1; ++i) {
//        cout << res[i] << endl;
//    }
    sort(res.begin(), res.end());
    int mi = res[0].val;
    printf("%d\n", mi);
    for (int i = 0; i < res.size(); ++i) {
        if (mi == res[i].val) {
            printf("%d ", res[i].id);
        } else break;
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

O(n^2logn)的算法.
不妨枚举一开始感染的节点作为根,然后进行树dp.
注意到病毒一定是向下传染的.
对于每个节点标记一个值,表示(感染这个节点后)感染这个节点引领的子树需要多久.
那么如何求出这个值?
设它为d[i],则我们要在第1单位时间传给某棵子树,在第2单位时间传给另一颗子树.....
于是,设它的子节点为j1,j2,...,jk,并且刚好是按照这个顺序传递的(即,先给j1,再给j2,j3...)
则d[i]=min(d[j1]+1,d[j2],d[j3]+3,.....,d[jk]+k);
注意根据排序不等式,想要这个结果最小,那么d[j]应该按照降序排列
拿一个栈存储每个子节点的d值,直接sort排序,然后计算即可....

Code

const int INF=(1<<30)-1;

struct edge
{
int in;
edge*nxt;
}pool[2050];
edge*et=pool;
edge*eds[1050];
void addedge(int i,int j)
{ et->in=j; et->nxt=eds[i]; eds[i]=et++; }
#define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)

int n;

bool used[1050];
int stk[1050],st;

int DFS(int x)
{
used[x]=true;

int tot=0;
int sl=st;
FOREACH_EDGE(i,x)
if(!used[i->in])
{
tot++;
stk[st++]=DFS(i->in);
}

if(tot==0) { used[x]=false; return 0; }

sort(stk+sl,stk+st);

int cost=0;
for(int i=0;i<tot;i++)
cost=max(cost,stk[sl+i]+tot-i);

st=sl;

used[x]=false;
return cost;
}

int r[1050],rt;

int main()
{
n=getint();
if(n==0) { printf("0\n\n"); return 0; }

for(int i=2;i<=n;i++)
{
int a=getint();
addedge(i,a);
addedge(a,i);
}

int res=INF;
rt=0;
for(int i=1;i<=n;i++)
{
int v=DFS(i);
if(v<=res)
{
if(v<res) rt=0,res=v;
r[rt++]=i;
}
}

printf("%d\n",res+1);
for(int i=0;i<rt;i++)
printf("%d ",r[i]);
printf("\n");

return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2736 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2736 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2732 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2736 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2732 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 2736 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 2736 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 2736 KiB, score = 10
测试数据 #8: Accepted, time = 124 ms, mem = 2736 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 2732 KiB, score = 10
Accepted, time = 356 ms, mem = 2736 KiB, score = 100
代码
const
maxn=1010;
type
aa=array[0..maxn]of integer;
var
f,f1:aa;
flag:array[0..maxn]of boolean;
a:array[0..maxn]of aa;
n,ans:integer;

procedure init;
var
i,x:integer;
begin
read(n);
for i:=2 to n do
begin
read(x);
inc(a[x,0]);
a[x,a[x,0]]:=i;
inc(a[i,0]);
a[i,a[i,0]]:=x;
end;
end;

procedure swap(var x,y:integer);
var
t:integer;
begin
t:=x;
x:=y;
y:=t;
end;

function max(x,y:integer):integer;
begin
if x>y then exit(x);
exit(y);
end;

procedure sort(var a:aa;l,r:integer);
var
i,j,z:integer;
begin
i:=l;
j:=r;
z:=f[a[(l+r)>>1]];
repeat
while f[a[i]]>z do
inc(i);
while f[a[j]]<z do
dec(j);
if i<=j then
begin
swap(a[i],a[j]);
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(a,i,r);
if j>l then sort(a,l,j);
end;

procedure dfs(x:integer);
var
i,t:integer;
begin
for i:=1 to a[x,0] do
if flag[a[x,i]]=false then
begin
flag[a[x,i]]:=true;
dfs(a[x,i]);
flag[a[x,i]]:=false;
end;
f[x]:=1;
sort(a[x],1,a[x,0]);
t:=0;
for i:=1 to a[x,0] do
if flag[a[x,i]]=false then
begin
inc(t);
f[x]:=max(f[x],t+f[a[x,i]]);
end;
end;

procedure work;
var
i:integer;
begin
ans:=maxn;
for i:=1 to n do
begin
fillchar(f,sizeof(f),1);
flag[i]:=true;
dfs(i);
flag[i]:=false;
f1[i]:=f[i];
if ans>f[i] then ans:=f[i];
end;
writeln(ans);
for i:=1 to n do
if f1[i]=ans then write(i,' ');
end;

begin
init;
work;
end.

树形dp、、注意，这题不是ural的1056，不是求树的中心，（即，不是求最长链）dfs每个点，然后对于子节点和父节点，时间长的先传染，就可以了。ps：注意特殊的链状结构。。。初始化一定要写好。。。因为这个第一个数据wa了一次。。。。。

树形dp，枚举每个点为根进行dfs，子节点dp值最大的先传染

ls的枚举过的料？

直接枚举+暴力+递归+弱弱的数据=AC

原题是Ural1056

树型DP+2次动归

第一次动规做f[i]:=max(f[son])+1，第二次动规做f[i]:=max(f[i],f[father]+1) 。

但是存在一个问题就是如果f[father]的值是从i那里得到的，这样计算显然就错了。

不要放弃，在实际操作过程中，f需要记下两个值，一个是最优值，一个是次优值，这两个值必须由不同的子结点得到。这样当最优值发生矛盾的时候，次优值一定不会矛盾。问题就解决了。复杂度O(N)十分的理想。

谁给个题解,这个树型DP怎么搞....虽然比赛时看出来是树型DP，但没想出来....

树形DP……

第一次数组开100，错误216

第二次改200，过了……

贪心+BFS=70分。

sofa...

.....

树形动归。。。。

。。。板凳都没了O.O

先看看标题~~

比赛题

OTL……