How to update path with Euler Tour?

Revision en19, by ak2k8, 2024-11-19 18:10:45

Recently, I've just encountered this problem:

$$$ $$$

Given a tree with $$$n$$$ vertices and rooted at $$$1$$$. Each vertex has an initial value, and initially, all these values are $$$0$$$.

$$$ $$$

There are $$$q$$$ queries of two types:

$$$ $$$
  • "1 u": Find the sum of values of vertices in the subtree rooted at u.
$$$ $$$
  • "2 u": Find the value at vertex u.
$$$ $$$
  • "3 u v x": Increase the values of vertices on the simple path from u to v by x.
$$$ $$$

Answer the queries of type 1 and 2.

$$$ $$$

Constraints

$$$ 1 \leq n,q \leq 200000 $$$
$$$ 1 \leq u,v \leq n $$$
$$$ 0 \leq |x| \leq 1000000 $$$

Are there any tricks to handle these types of queries with Euler Tour? I've thought about this problem for several days and haven't come up with any idea how to do it yet because of the update path queries.

Tags euler tour

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en24 English ak2k8 2024-11-19 18:19:28 84
en23 English ak2k8 2024-11-19 18:13:20 0 (published)
en22 English ak2k8 2024-11-19 18:12:16 78
en21 English ak2k8 2024-11-19 18:11:43 8 Tiny change: 'problem:$\\$\nGiven a' -> 'problem:$\newline$\nGiven a'
en20 English ak2k8 2024-11-19 18:11:30 7 Tiny change: 's problem:\n$$ $$\nGiven a' -> 's problem:$\\$\nGiven a'
en19 English ak2k8 2024-11-19 18:10:45 210
en18 English ak2k8 2024-11-19 18:06:33 43
en17 English ak2k8 2024-11-19 18:05:57 1 Tiny change: 'oblem:\n$$ $$\nGiven ' -> 'oblem:\n$$$$\nGiven '
en16 English ak2k8 2024-11-19 18:05:40 3 Tiny change: 'oblem:\n$$\\$$\nGiven ' -> 'oblem:\n$$ $$\nGiven '
en15 English ak2k8 2024-11-19 18:05:25 4 Tiny change: 'problem:\n\\\nGiven a ' -> 'problem:\n$$\\$$\nGiven a '
en14 English ak2k8 2024-11-19 18:05:09 2 Tiny change: 'problem:\n$\\$\nGiven a ' -> 'problem:\n\\\nGiven a '
en13 English ak2k8 2024-11-19 18:04:36 1 Tiny change: 'blem:\n$\\\$\nGiven' -> 'blem:\n$\\$\nGiven'
en12 English ak2k8 2024-11-19 18:04:21 2 Tiny change: 'problem:\n\\\\nGiven a ' -> 'problem:\n$\\\$\nGiven a '
en11 English ak2k8 2024-11-19 18:04:08 3 Tiny change: ' problem:\\\nGiven ' -> ' problem:\n\\\\nGiven '
en10 English ak2k8 2024-11-19 18:03:48 49
en9 English ak2k8 2024-11-19 18:01:45 4 Tiny change: 's problem:\ncut\nGiven a ' -> 's problem:[cut]\nGiven a '
en8 English ak2k8 2024-11-19 18:01:30 2 Tiny change: 'problem:\n[cut]\nGiven a ' -> 'problem:\ncut\nGiven a '
en7 English ak2k8 2024-11-19 18:01:15 49
en6 English ak2k8 2024-11-19 17:59:00 20
en5 English ak2k8 2024-11-19 17:58:18 26
en4 English ak2k8 2024-11-19 17:56:59 12
en3 English ak2k8 2024-11-19 17:56:26 2 Tiny change: 'ree with $$n$$ vertices' -> 'ree with $n$ vertices'
en2 English ak2k8 2024-11-19 17:56:03 30
en1 English ak2k8 2024-11-19 17:54:56 597 Initial revision (saved to drafts)