問題一覧 > 通常問題

No.2163 LCA Sum Query

レベル : / AI推定難易度 : 2750 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 16
作問者 : akakimidori / テスター : hotman78
お気に入りにしたユーザー ProblemId : 8567 / 自分の提出
問題文最終更新日: 2022-12-13 18:58:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2022 (順位表) の他の問題:

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$

  • $1 \leq N \leq 5 \times 10^4$
  • $1 \leq Q \leq 10^5$
  • $1 \leq A_i, B_i \leq N$
  • $1 \leq U_i, R_i, V_i \leq N$
  • All input values are integers.
  • The given graph is a tree.
  • 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もしくは右上の雲マークをクリックしてアカウントを作成してください。