No.2163 LCA Sum Query
タグ : / 解いたユーザー数 16
作問者 :
akakimidori
/ テスター :
hotman78
Problem Statement
You are given a tree $T$ with $N$ vertices. The vertices are numbered from $1$ to $N$. The $i$-th edge connects vertices $A_i$ and $B_i$.
There is also a set $S$ consisting of integers from $1$ to $N$. Initially, $S$ is empty.
Define the function $\mathrm {LCA}_T(r, x, y) (1 \leq r, x, y \leq N)$ as follows.
$\mathrm {LCA}_T(r, x, y) =$ the vertex number of the lowest common ancestor of vertices $x$ and $y$ when the tree $T$ is regarded as a rooted tree with root $r$
Process the following queries.
u r v: If $u$ is not contained in $S$, add $u$ to $S$. If $u$ is contained in $S$, remove $u$ from $S$. Then, letting$X = \{x| x \in S, \mathrm {LCA}_T(r, v, x) = v\}$
, output
$\displaystyle \sum_{a \in X} \sum_{\substack{b \in X \\ a < b}} \mathrm {LCA}_T(r, a, b)$ .
Input
$N\ Q$
$A_1\ B_1$
$\vdots$
$A_{N - 1}\ B_{N - 1}$
$U_1\ R_1\ V_1$
$\vdots$
$U_Q\ R_Q\ V_Q$
Output
Output $Q$ lines. The $i$-th line should contain the answer to the $i$-th query. Output a newline at the end.
Sample
Sample 1
Input
3 5 2 1 1 3 3 1 2 2 1 1 1 3 3 1 3 1 1 1 1
Output
0 1 7 0 3
In the 1st query, $S = \{3\}, X = \{\}$. No pair $(a, b) (a < b)$ can be formed, so output $0$.
In the 2nd query, $S = \{2, 3\}, X = \{2, 3\}$. Since $\mathrm {LCA}_T (1, 2, 3) = 1$, output $1$.
In the 3rd query, $S = \{1, 2, 3\}, X = \{1, 2, 3\}$. Since $\mathrm {LCA}_T (3, 1, 2) = 1, \mathrm {LCA}_T (3, 1, 3) = 3, \mathrm {LCA}_T (3, 2, 3) = 3$, output their sum, $7$.
In the 4th query, $S = \{2, 3\}, X = \{2\}$. No pair $(a, b) (a < b)$ can be formed, so output $0$.
In the 5th query, $S = \{1, 2, 3\}, X = \{1, 2, 3\}$. Since $\mathrm {LCA}_T (1, 1, 2) = 1, \mathrm {LCA}_T (1, 1, 3) = 1, \mathrm {LCA}_T (1, 2, 3) = 1$, output their sum, $3$.
Sample 2
Input
7 13 6 2 4 6 6 1 7 2 3 7 7 5 4 2 2 5 5 5 2 6 6 1 4 2 7 4 7 1 3 2 3 2 2 7 1 1 4 1 7 3 6 2 2 6 3 2 1 2 6 5 7
Output
0 5 14 2 7 2 35 29 7 2 0 2 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。