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)? Hi. This is my solution for this problem. Let's find two farthest nodes in tree. Let's call it f1 and f2. It can be done by two bfs'. Now let's answer for queries. Let the y farthest node from x(it's f1 or f2). If such node exists that dist(x, z) = d, then it would lie on path from x to y. If dist(x, y) < d, answer would be 0. Let l be lca(x, y). If dist(l, x) <= d, answer would be dist(l, x)'th parent of x. If x is ancestor of y, answer would be (dist(x, y) - d)'th parent of y. Otherwise answer would be dist(l, y) - (d - dist(l, x)). Sorry for my poor English. O(N*log(N)), ~100 lines of code, ~1K gzipped For every edge out of a node we calculate L, the length of the longest path from this node thru the edge. It is two DFS: the first one to calculate L for downward edges, the second one to fix the upward edges. At most two edges (with the largest L) of each node are needed to calculate the longest paths (the second is needed for the situations where we get from node A into node B and in node B the edge B->A has the maximal L). For these two edges we precalculate short-cuts: for all i, such that 2^i ≤ L, we save the node C that can be reached after 2^i steps and from which edge in C it was reached. My solution is quite simple, just find one farthest nodes pair in the tree by two DFSs, denoting f1 and f2. Then use f1 as root and dfs to calculate the 2^i steps' father of every node x. And use f2 as root similarly. Then the answer can be done by express d to the binary form and jump at most log(n) to find an answer under these two roots. We can actually solve it on just O(N) time. Let's set vertex 1 as a root. Now let's at first find the depths of subtree of each vertex, deepest vertex in each subtree and the distance from the root for each vertex. This can be done in one DFS. Let's name them as: 1) depth[ver] -> depth of a subtree of vertex ver 2) dist[ver] -> distance from vertex 1 to vertex ver 3) mx_ver[ver] -> deepest vertex in a subtree of vertex ver Now we can check for all queries: 1) If query is (v, d) and depth of vertex v is >= d, then the answer is the parent of vertex mx_ver[v] on distance (depth[v] - d) (so we should somehow later go up from vertex v to (depth[v] - d) edges). Let's store it in mx_ver[v]. 2) If query is (v, d) and distance from root to v >= d (so dst[v] >= d), then the answer is the parent of vertex v on distance d, let's store this information in vertex v. What should we do with all the other queries? All other queries (v, d) tell us that the answer for them will look somehow like this: Take vertex v, go up several edges, then go down to some other subtree. So we need to take some ancestor of v and go into it to a subtree different from a subtree containing vertex v. Let's say that this ancestor is some vertex u and the depth of its deepest subtree not containing v is H. Then if (dst[v] - dst[u] + H) >= d, we can choose u as a suitable ancestor. And the answer for the query will be the parent of the deepest vertex in subtree H on distance d - (dst[v] - dst[u] + H). Great thing about these formulas is that if we stay in some vertex v during some DFS, for all our ancestors the number (H - dst[u]) is a constant and we can keep the maximum value of it on current path. So what should we do next? Let's simply run one more DFS. During our walk through the tree in the DFS let's keep maximum value of (H - dst[u]) for all our ancestors. To do this we need to do some routine stuff: 1) Calculate two maximums by depth[to] + 1 for all children (if we will go to the subtree with first maximum, we will use H - dst from the second one). 2) Before going into some child check if the new found values are larger then global maximum (H - dst[u]). 3) Not forget to carefully restore this global maximum going up on each step. 4) Each time we take new maximum for (H - dst[u]), also store the deepest vertex in the subtree H. Then in each vertex during this DFS we also need to iterate through all remaining queries for this vertex and try to set an answer to them, again in form "Answer for this query is a parent of some deepest vertex in some subtree H on distance (dst[v] + (H - dst[u])) - d" The final step would be to run one more DFS and in all vertices with stored info "go up to distance X" do this by simply storing current DFS path and writing needed parent as an answer for the corresponding query. 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 Can someone know the 9th test? the topic is closed, a simple bug 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 ok, ac now - i count LOG2N variable as floor(log2n) but i should set it ceil(log2n); Thanks! I was wondering why I got WA until I saw your reasons. It gave me spirit,now I have got deeper realization of this problem. Edited by author 01.12.2016 19:04 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 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. give me some tests , please ! up This test help me 10 1 1 2 2 3 3 4 4 5 1 6 6 7 1 8 8 9 9 10 10 7 |
|