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)?

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.

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

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.

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.