How to update path with Euler Tour? - Codeforces

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

How to update path with Euler Tour?

Revision en5, by ak2k8, 2024-11-19 17:58:18

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