How to update path with Euler Tour?

Правка en24, от ak2k8, 2024-11-19 18:19:28

Recently, I've just encountered this problem:$$$\newline$$$ Given a tree with $$$n$$$ vertices and rooted at $$$1$$$. Each vertex has an initial value, and initially, all these values are $$$0$$$.$$$\newline$$$ There are $$$q$$$ queries of two types:$$$\newline$$$ - "1 u": Find the sum of values of vertices in the subtree rooted at u.$$$\newline$$$ - "2 u": Find the value at vertex u.$$$\newline$$$ - "3 u v x": Increase the values of vertices on the simple path from u to v by x.$$$\newline$$$ Answer the queries of type 1 and 2.$$$\newline$$$ Constraints:

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

Time Limit:

$$$ 0.5s $$$

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. And with this time limit, I think HLD can't pass :<

Теги euler tour

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en24 Английский ak2k8 2024-11-19 18:19:28 84
en23 Английский ak2k8 2024-11-19 18:13:20 0 (published)
en22 Английский ak2k8 2024-11-19 18:12:16 78
en21 Английский ak2k8 2024-11-19 18:11:43 8 Tiny change: 'problem:$\\$\nGiven a' -> 'problem:$\newline$\nGiven a'
en20 Английский ak2k8 2024-11-19 18:11:30 7 Tiny change: 's problem:\n$$ $$\nGiven a' -> 's problem:$\\$\nGiven a'
en19 Английский ak2k8 2024-11-19 18:10:45 210
en18 Английский ak2k8 2024-11-19 18:06:33 43
en17 Английский ak2k8 2024-11-19 18:05:57 1 Tiny change: 'oblem:\n$$ $$\nGiven ' -> 'oblem:\n$$$$\nGiven '
en16 Английский ak2k8 2024-11-19 18:05:40 3 Tiny change: 'oblem:\n$$\\$$\nGiven ' -> 'oblem:\n$$ $$\nGiven '
en15 Английский ak2k8 2024-11-19 18:05:25 4 Tiny change: 'problem:\n\\\nGiven a ' -> 'problem:\n$$\\$$\nGiven a '
en14 Английский ak2k8 2024-11-19 18:05:09 2 Tiny change: 'problem:\n$\\$\nGiven a ' -> 'problem:\n\\\nGiven a '
en13 Английский ak2k8 2024-11-19 18:04:36 1 Tiny change: 'blem:\n$\\\$\nGiven' -> 'blem:\n$\\$\nGiven'
en12 Английский ak2k8 2024-11-19 18:04:21 2 Tiny change: 'problem:\n\\\\nGiven a ' -> 'problem:\n$\\\$\nGiven a '
en11 Английский ak2k8 2024-11-19 18:04:08 3 Tiny change: ' problem:\\\nGiven ' -> ' problem:\n\\\\nGiven '
en10 Английский ak2k8 2024-11-19 18:03:48 49
en9 Английский ak2k8 2024-11-19 18:01:45 4 Tiny change: 's problem:\ncut\nGiven a ' -> 's problem:[cut]\nGiven a '
en8 Английский ak2k8 2024-11-19 18:01:30 2 Tiny change: 'problem:\n[cut]\nGiven a ' -> 'problem:\ncut\nGiven a '
en7 Английский ak2k8 2024-11-19 18:01:15 49
en6 Английский ak2k8 2024-11-19 17:59:00 20
en5 Английский ak2k8 2024-11-19 17:58:18 26
en4 Английский ak2k8 2024-11-19 17:56:59 12
en3 Английский ak2k8 2024-11-19 17:56:26 2 Tiny change: 'ree with $$n$$ vertices' -> 'ree with $n$ vertices'
en2 Английский ak2k8 2024-11-19 17:56:03 30
en1 Английский ak2k8 2024-11-19 17:54:56 597 Initial revision (saved to drafts)