Try

12 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 9
9 10
10 11
11 12
2 6

Why is there such a big difference between these two compilers and how do I know if I have solved this problem, it just feels like I wrote really dirty code and it somehow worked.

If you're having trouble with WA 5 or WA 6, try this test:

10 1
2 1
3 2
4 3
5 2
6 3
7 2
8 2
9 3
10 8
9 2

Correct answer is 2, 4 or 6.

I got AC with O(N*sqrt(N)),but my solution is very hard(274 lines and many different subtasks). Who can say simple solution(idea without code)?

The problem says the program only needs to print out any of the answers.
but why i WA in the first test but can pass all my tests?

9 3
1 5
1 4
2 7
2 5
3 6
5 9
6 9
7 8
1 4
2 4
9 4

Answer:
8 (or 3)
3
8

try this test:
21 1
1 2
2 3
3 4
4 5
4 6
6 7
7 8
5 9
9 10
10 11
11 12
1 13
12 14
14 15
15 16
13 17
16 18
18 19
19 20
20 21
8 15

answer:
21

help me

Can someone know the 9th test?

2 1
3 1
4 3
5 1
6 4
7 2
8 6
9 8
10 7
ans: 8 or 1

I'm searching the farest node for each node via one dfs and then try to answer the query using this information:

1) if(query_dist > distance_to_farest_node_from_query_vertex)
output 0
2) if query_vertex is ancestor of it's farest node then i return go_up_from(farest_node_from_query_vertex,
dist_to_far_node  -  query_dist)
3) if dist to lca(query_vertex,farest_node_from_query_vertex) enough (d(lca)>=query_dist) just go up from query_vertex in query_dist steps.
4) if(dist to lca is not enough) then go_up_from(
farest_node, farest_node_dist  -  query_dist)
my programm passes my tricky tests,sample test and test from thread. Pls, somebody, give me more tricky tests!

Edited by author 10.10.2010 22:43

My program outputs the following on test 1:

0
1
9
3
4
4
4
4
4
1

and I get WA1. However if I use G++ 2011 on the same code then I pass test 1 and get TLA on test 8.

Please somebody provide some more test cases ...

I have tested this code many times, it answers to all my tests correctly.

UPD: AC now !!!
Bug was here:
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j < POW; ++j)
        {
            up[i][j]=up[up[i][j - 1]][j - 1];
        }
    }
must be:
    for (j = 1; j < POW; ++j)
    {
        for (i = 1; i <= n; ++i)
        {
            up[i][j]=up[up[i][j - 1]][j - 1];
        }
    }


Edited by author 25.04.2013 18:21

Если у вас TL 21 то попробуйте тест у которого корень с 19999 сыновей. Это именно такой тест

try this case?
10 10
2 1
3 2
4 3
5 2
6 3
7 2
8 2
9 3
10 8
2 3
2 3
3 3
3 2
1 0
1 9
5 9
8 2
9 2
8 7

tell me any test

test1:
1 2
1 0
1 1

test2:
2 6
2 1
1 0
1 1
1 2
2 0
2 1
2 2

This is my code, help me with some wrong tests , please ^^
Program Tree2;
Uses    Math;//,crt;
Const   Finp    ='';//
        Fout    ='';
        Maxn    =20001;
Type    Pt      =^rc;
                rc=Record
                 v:Longint;
                 Next:Pt;
                 End;
Var     fi,fo   :Text;
        n,k,Low,S,T:Longint;
        List    :Array[1..Maxn] of Pt;
        A,C,tr,v1,v2,Q,B,F:Array[1..Maxn] of Longint;
        Free    :Array[1..Maxn] of Boolean;
Procedure       OpenFile;
Begin
        Assign(fi,finp); Reset(fi);
        Assign(fo,fout); Rewrite(fo);
End;
Procedure       CloseFile;
Begin
        Close(fi); Close(fo);
End;
Procedure       Push(v:Longint; Var Next:pt);
Var     p:pt;
Begin
        New(p);
        p^.Next:=Next;
        p^.v:=v;
        Next:=p;
End;
Procedure       Readinp;
Var     u,v:Longint;
Begin
        Readln(fi,n,k);
        If n=1 Then
        Begin
                For k:=1 to k do
                Begin
                        Read(fi,u,v);
                If v=0 Then WRiteln(fo,1)
                else Writeln(fo,0);
                End;
                CloseFile;
                Halt;
        End;
        For n:=1 to n do List[n]:=Nil;
        For n:=2 to n do
        Begin
                Readln(fi,u,v);
                Push(u,List[v]);
                Push(v,List[u]);
        End;
End;
Procedure       Dfs(i,x:Longint);
Var     p:Pt;
        v:Longint;
Begin
        If Low < x Then
        Begin
                Low:=x; S:=i;
        End;
        Free[i]:=False;
        p:=List[i];
        While p<> Nil do
        Begin
                v:=p^.v;
                If Free[v] then
                Begin
                        Tr[v]:=i;
                        Dfs(v,x+1);
                End;
                p:=p^.Next;
        End;
End;
Procedure       Prepare;
Var     i,x:Longint;
Begin
        Fillchar(Free,sizeof(Free),True);
        Dfs(1,0);
        Low:=0; T:=S;
        Fillchar(Free,sizeof(Free),True);
        Fillchar(Tr,sizeof(Tr),0);
        DFS(T,0);
        i:=S; x:=1; C[S]:=1; B[1]:=S;
        While True do
        Begin
                i:=Tr[i];
                Inc(x); C[i]:=x; B[x]:=i;
                If i = T Then Break;
        End;
End;
Procedure       Solve;
Var     i,x,dau,cuoi,w,v:Longint;
        p:pt;
Begin
        Inc(Low);
        For i:=1 to Low do
        Begin
                x:=b[i];
                dau:=0; cuoi:=1; Q[1]:=x;
                While dau <> cuoi do
                Begin
                        Inc(dau); w:=Q[dau];
                        p:=List[w];
                        While p<> Nil do
                        Begin
                                v:=p^.v;
                                If (C[v]=0) Then
                                 if (v1[v]=0) Then
                                 Begin
                                        v1[v]:=x;
                                        v2[v]:=v2[w]+1;
                                        Inc(cuoi); Q[cuoi]:=v;
                                 End;
                                p:=p^.Next;
                        End;
                End;
        End;
End;
Function        Found(k,u,l:Longint):Longint;
Var     dau,cuoi,v,x:Longint;
        p:Pt;
Begin
        dau:=0; cuoi:=1;
        F[u]:=0; Q[1]:=u;
        Tr[u]:=k;
        While dau<> cuoi do
        Begin
                Inc(dau); x:=Q[dau];
                p:=List[x];
                While p<> Nil do
                Begin
                        v:=p^.v;
                        If Tr[v] <> k Then
                        Begin
                                F[v]:=F[x]+1;
                                Tr[v]:=k;
                                Inc(cuoi); Q[cuoi]:=v;
                                If F[v]=l Then Exit(v);
                        End;
                        p:=p^.Next;
                End;
        End;
        Exit(0);
End;
Procedure       Answer;
Var     u,v,x,Ans:Longint;
Begin
        Fillchar(tr,sizeof(Tr),0);
        For k:=1 to k do
        Begin
                Readln(fi,u,v);
                If v >= Low Then
                Begin
                        Writeln(fo,0);
                        Continue;
                End;
                If C[u] <> 0 Then
                Begin
                        If v + C[u] <= Low Then
                        Begin
                                v:=v+ C[u];
                                Writeln(fo,B[v]);
                                Continue;
                        End;
                        If v<C[u] Then
                        Begin
                                v:=C[u]-v;
                                Writeln(fo,B[v]);
                                COntinue;
                        End;
                        Writeln(fo,0);
                        Continue;
                End;
                If v2[u]=v Then
                Begin
                        Writeln(fo,v1[u]);
                        Continue;
                End;
                If V2[u] < v Then
                Begin
                        x:=C[v1[u]];
                        If x > v - V2[u] Then
                        Begin
                                x:=x-(v - v2[u]);
                                Writeln(fo,B[x]);
                                Continue;
                        End;
                        If x + (v- v2[u]) <= Low Then
                        Begin
                                x:=x+(v-v2[u]);
                                Writeln(fo,B[x]);
                                Continue;
                        End;
                        Writeln(fo,0);
                        Continue;
                End;
                x:=Found(-k,u,v);
                Writeln(fo,x);
        End;
End;
Function        Dist(u,l:Longint):Longint;
Var     dau,cuoi,v,x:Longint;
        p:Pt;
Begin
        dau:=0; cuoi:=1;
        F[u]:=0; Q[1]:=u;
        Tr[u]:=k;
        While dau<> cuoi do
        Begin
                Inc(dau); x:=Q[dau];
                p:=List[x];
                While p<> Nil do
                Begin
                        v:=p^.v;
                        If Tr[v] <> k Then
                        Begin
                                F[v]:=F[x]+1;
                                Tr[v]:=k;
                                Inc(cuoi); Q[cuoi]:=v;
                                If v=l Then Exit(F[v]);
                        End;
                        p:=p^.Next;
                End;
        End;
        Exit(0);
End;
Procedure       Test;
Var     u,v,l,x:Integer;
Begin
        Assign(fi,finp); Reset(fi);
        Assign(fo,fout); Reset(fo);
        Readln(fi,n,k);
        For n:=2 to n do Readln(fi,u,v);
        For k:=1 to k do
        Begin
                Readln(fi,u,l);
                Readln(fo,v);
                If v=0 Then
                Begin
                        x:=Found(-k,u,l);
                        If x<>0 Then
                        Begin
                                Writeln('sai');
                                Exit;
                        End;
                        COntinue;
                End;
                x:=Dist(u,v);
                Writeln(x,' ',l);
                If x<>l Then
                begin
                        Writeln('Sai');
                        Exit;
                End;
        End;
End;
Begin
//        Clrscr;
        Openfile;
        Readinp;
        Prepare;
        Solve;
        Answer;
        CloseFile;
//        Test;
End.