How to update path with Euler Tour?

Revision en2, by ak2k8, 2024-11-19 17:56:03

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 $$$
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)