Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя invisible00420

Автор invisible00420, история, 9 лет назад, По-английски

Please give me any hint or solution for this problem.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  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.