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
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
Thank you !!
even solved it without the spoilers :p
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)
It have to be "if X is NOT an ancestor of Y", right?
i think he means X is a child of Y
Actually I meant "if Y is an ancestor of X". Sorry for that. (It's hard to edit in mobile..)
any idea why this gets WA , can't seem to find the error :/