| Show all threads Hide all threads Show all messages Hide all messages | | For WA6 | bashNewbie | 1752. Tree 2 | 2 Sep 2023 11:48 | 1 | For WA6 bashNewbie 2 Sep 2023 11:48 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 i have Runtime error (stack overflow) with Visual C++ x64, but AC with G++ 9.2? | >>> | 1752. Tree 2 | 6 Jul 2022 05:24 | 1 | 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. | | WA 5/6 test case | Risminator | 1752. Tree 2 | 9 Apr 2022 02:51 | 1 | 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. | | Good problem! | Felix_Mate | 1752. Tree 2 | 18 Feb 2022 01:07 | 5 | 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. | | Special Judge? | fishpear | 1752. Tree 2 | 24 Dec 2021 16:14 | 2 | 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? | | If you WA at test 6, this test may help you | Dylan Harris | 1752. Tree 2 | 25 Jun 2020 15:10 | 1 | 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 | | If you wa on test 5 | binario | 1752. Tree 2 | 21 Dec 2019 11:31 | 1 | 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 WA16 | Killer Frost | 1752. Tree 2 | 31 Mar 2018 17:38 | 1 | | | WA 9 | Wlad | 1752. Tree 2 | 20 Nov 2017 13:54 | 2 | WA 9 Wlad 19 Nov 2017 01:45 Can someone know the 9th test? the topic is closed, a simple bug | | WA test 5. Here is my case | Dang Quang Huy | 1752. Tree 2 | 1 Aug 2017 21:16 | 1 | 2 1
3 1
4 3
5 1
6 4
7 2
8 6
9 8
10 7
ans: 8 or 1 | | WA 10 | Baurzhan | 1752. Tree 2 | 1 Dec 2016 19:04 | 3 | WA 10 Baurzhan 10 Oct 2010 22:41 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 | | something is wrong with the checker for visual c++ 2010 | the_swede | 1752. Tree 2 | 3 Sep 2014 16:31 | 1 | 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. | | WA on Test 5 | chang | 1752. Tree 2 | 14 Jan 2014 06:55 | 1 | Please somebody provide some more test cases ... | | WA 6 ? | bayram | 1752. Tree 2 | 20 Jun 2013 18:49 | 1 | WA 6 ? bayram 20 Jun 2013 18:49 | | Why WA5? The code is here: | Harhro94 [Hrayr Harutyunyan] | 1752. Tree 2 | 25 Apr 2013 16:59 | 1 | 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 | ibra (TNU) | 1752. Tree 2 | 9 Sep 2012 04:13 | 1 | TL 21 ibra (TNU) 9 Sep 2012 04:13 Если у вас TL 21 то попробуйте тест у которого корень с 19999 сыновей. Это именно такой тест | | If you wa on test 6 | XxX_Stu | 1752. Tree 2 | 29 Aug 2012 12:14 | 1 | 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 | | WA 5 | minda ro bednieri iyo | 1752. Tree 2 | 16 Aug 2012 14:37 | 1 | WA 5 minda ro bednieri iyo 16 Aug 2012 14:37 | | WA2 and WA3 - hardcore tests | luckysundog | 1752. Tree 2 | 10 Mar 2011 22:53 | 1 | test1:
1 2
1 0
1 1
test2:
2 6
2 1
1 0
1 1
1 2
2 0
2 1
2 2 | | wa #5 , can anyone give some testcases ? thanks | Ctna | 1752. Tree 2 | 9 Nov 2010 08:33 | 3 | 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 |
|
|
