ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1752. Tree 2

WA 10
Posted by 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
Re: WA 10
Posted by Baurzhan 11 Oct 2010 10:19
ok, ac now  - i count LOG2N variable as floor(log2n) but i should set it ceil(log2n);
Re: WA 10
Posted by igoodvegetablea 1 Dec 2016 19:04
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