svg_af's blog

Dynamically rooted trees ?
By svg_af, history, 9 years ago, In English

Hello there

so i found this problem on spoj

we have a tree where each node has an integer weight and two types of queries

1- print sum of weights in subtree of given node

2- change root to given node

now first type of queries is no issue if the root is fixed ... i would solve it with segment tree, but changing the root kinda ruins everything

any hints about how i should think about this would be really appreciated :D

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

The answer is always size of subtree or size of all tree minus subtree.

For each query you just need to determine edge that goes to current root.

More spoilers in previous revision

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank you !!

    even solved it without the spoilers :p

    → Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it +6 Vote: I do not like it

Fix the root with 1.

If the root is changed to X, we can determine node Y's subtree size as -

  • if X is Y, answer is N.

  • if X is an ancestor of Y, answer is N — (Y's child's subtree size which contains node X)

  • otherwise, answer is Y's subtree size.

solving case #1 and #3 are trivial.

case #2 can be solved by binary searching the child of Y.

time = O(N + QlgN)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It have to be "if X is NOT an ancestor of Y", right?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      i think he means X is a child of Y

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Actually I meant "if Y is an ancestor of X". Sorry for that. (It's hard to edit in mobile..)

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    any idea why this gets WA , can't seem to find the error :/

    → Reply