stillcoding's blog

Segment Tree With Trees?
By stillcoding, history, 9 years ago, In English

Hello Codeforces

I want to represent (Tree) inside Segment Tree.

For Example: Given Tree, There are two queries:

1 — Change all the vertices value on the path from (u — v) by x.

2 — Calculate the sum for the vertices value on the path from (u — v) and print it.

I have no idea how to represent the tree inside the segment tree, any ideas?

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

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

Heavy Light Decomposition is what you're looking for:

Btw, did you create a new account to ask a question? If so, why?

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

You can do this using heavy-light decompostion + segment tree with lazy propagation on each of path.

Too late :(

→ Reply