invisible00420's blog

How to solve this problem of graphs??
By invisible00420, history, 9 years ago, In English

Please give me any hint or solution for this problem.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. choose the root of tree
  2. calculate h[v] — distance from root to v. Need ignore the direction of the edges.
  3. then set the weight of edge (a->b) to 1 and weight of edge (b->a) to -1.
  4. calculate s[v] — the sum of weights from root to v.

If vertex p is the parent of v and (h[v]-h[p]) = (s[v]-s[p]), it means that all edges from p to v directed from p to v.

If vertex p is the parent of v and (h[v]-h[p]) = -(s[v]-s[p]), it means that all edges from p to v directed from v to p.

For every query (a,b):

  1. p = L(a,b)
  2. check that edges from a to p directed to p, and check that edges from p to b directed to b

Sorry for my english.

→ Reply