3717 . [模板題] Dynamic Graph Vertex Add Component Sum
TopCoder
Tags
Description
You are given an empty graph with $N$ vertices. The $i$-th vertex has a value $a_ i$ written on it.
Process $Q$ queries:
0 u v: Add an edge between vertex $u$ and vertex $v$. (It is guaranteed that, immediately before this query, there is no edge between vertex $u$ and vertex $v$)1 u v: Remove the edge between vertex $u$ and vertex $v$. (It is guaranteed that, immediately before this query, there is an edge between vertex $u$ and vertex $v$)2 v x: $a_ v \gets a_ v + x$3 v: Output the sum of values on all vertices that are connected to vertex $v$ by a path.
Input Format
$N$ $Q$
$a_ 0$ $a_ 1$ ... $a_ {N - 1}$
$\textrm{Query}_ 0$
$\textrm{Query}_ 1$
:
$\textrm{Query}_ {Q - 1}$
Output Format
Sample Input 1
5 16 1 10 100 1000 10000 0 0 1 0 1 2 0 2 3 0 3 4 0 0 4 3 3 1 1 2 3 1 1 3 4 3 0 2 1 100000 3 1 0 1 4 3 2 0 3 4 3 0
Sample Output 1
11111 11111 10011 110011 1100 111111
Hints
- $1 \leq N, Q \leq 3 \times 10^ {5}$
- $0 \leq a_ i, x \leq 10^ {9}$
- $0 \leq u_ i, v_ i < N$
- $u_ i \neq v_ i$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|