It can be done easier , look here https://codeforces.com/blog/entry/17974?locale=ru

One possible solution is to find the most distant computer(let's call it x) from the first, and then start BFS from it. The path from the last added in the BFS and x is the longest tree chain. So the middle nodes are the wanted answer. (if the chain has odd number of nodes, the answer will be n/2, and if it's even they will be n/2 and n/2+1)

My soulotion is O(n^2) but TLE on test 9.Here is my soulution.

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int way[10001][2];

int ps_max(int start)      //Obxod(poisk) v shirinu
{
    int *label,i,p(0),k(1),*fifo,cur;
    label=new int [n];
    fifo=new int [n];
    for(i=0;i<n;i++)
    {
        label[i]=32767;
    }
    label[start]=0;
    int max=0;
    fifo[p]=start;
    while(p!=k)
    {
        cur=fifo[p];
        p++;
        for(i=0;i<n-1;i++)
        {
            if ((way[i][0]==cur || way[i][1]==cur))
            {
                if (way[i][0]==cur && label[way[i][1]]>label[cur]+1)
                {
                    label[way[i][1]]=label[cur]+1;
                    if (label[way[i][1]]>=max)
                    {
                        max=label[way[i][1]];
                    }
                    fifo[k]=way[i][1];
                    k++;
                }
                else if (way[i][1]==cur && label[way[i][0]]>label[cur]+1)
                {
                    label[way[i][0]]=label[cur]+1;
                    if (label[way[i][0]]>=max)
                    {
                        max=label[way[i][0]];
                    }
                    fifo[k]=way[i][0];
                    k++;
                }
            }
        }
    }
    return max;
}



int main()
{
    int i,t,min(100000);
    cin>>n;
    int *center;
    center=new int [n];
    for(i=1;i<n;i++)
    {
        cin>>t;
        t--;
        way[i-1][0]=t;
        way[i-1][1]=i;
    }
    for(i=0;i<n;i++)
    {
        center[i]=ps_max(i);
        if (center[i]<=min)
        {
            min=center[i];
        }
    }
    for(i=0;i<n;i++)
    {
        if (center[i]==min) cout<<i+1<<" ";
    }
    return 0;
}

Yes

remote - means the further

 what algo should i use,I had memory limit,then time limit and now again time limit 2.046s 1.037kb?

Hmmmmm....
O(n^2) is too slow (-_-).
I know  O(N+M) solution.You have just to delte leaves, while number of vertex>2.If you will do it righ,you will get O(N+M)solution.

1. the graph forms a tree
2. you need to give this tree direction (since the given tree is
undirected)
3. the longest path starting at node k is the maximum of 2 values:
the maximum path starting at k and going DOWN (a tree has no cycles
so you can solve this easily in linear time, i used simple DP)
and the maximum path by going UP from k.

Just cut off leafs of tree step by step while count of nodes >2!


Edited by author 25.06.2005 14:44

Far not the fastest solution, but passed (0.375 sec):
1. make a bidirectional graph, connectivity of which will be kept in an array of vectors
2. start dfs from each of the verticies which are not leaves and calculate the longest path
3. Note that if there are 2 vertices, the answer is always "1 2"
The solution might run in O(N*(N+M)) time, as I guess

Edited by author 15.02.2010 13:13

Edited by author 15.02.2010 13:13

YES, you are like salesman now.

Sorry,but now I know maybe there isn't a "legal" data that makes error.
I can't prove it well,but it's true:when use 2bfs,you needn't sort 2 num.
See:
Divide the tree into 2 parts,L and R.
The answer,if 2 num,must be in the longer part.Let's say it's on the right.
First you bfs to right,then bfs to leftmost.
When you follow the longest chain back again,you are going to right side.
If the data is legal,part R is in inscend(I don't know how to spell) order.So ans num1<ans num2.
so you needn't sort them at all!