問題一覧 > 通常問題

No.2163 LCA Sum Query

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : akakimidoriakakimidori / テスター : hotman78hotman78
1 ProblemId : 8567 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-13 18:58:39

問題文

$N$ 頂点の木 $T$が与えられます。 各頂点には $1$ から $N$ の番号がついています。 $i$ 番目の辺は 頂点 $A_i$ と $B_i$ をつないでいます。 

また $1$ から $N$ までの整数からなる集合 $S$ があります。 はじめ $S$ は空集合です。

関数 $\mathrm {LCA}_T(r, x, y) (1 \leq r, x, y \leq N)$ を次のように定めます。

    $\mathrm {LCA}_T(r, x, y) =$ 木 $T$ を $r$ を根とする根付き木として見た時の頂点 $x$ と頂点 $y$ の最小共通祖先の頂点番号

以下のクエリを処理してください

  • u r v: $u$ が $S$ に含まれていないなら $S$ に $u$ に追加する。 $u$ が $S$ に含まれているなら $S$ から $u$ を削除する。その後

    $X = \{x| x \in S, \mathrm {LCA}_T(r, v, x) = v\}$

    と置いた時の

    $\displaystyle \sum_{a \in X} \sum_{\substack{b \in X \\ a < b}} \mathrm {LCA}_T(r, a, b)$

    を出力する

入力

$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$
  • 入力はすべて整数
  • 与えられるグラフは木
  • 出力

    $Q$ 行出力してください。$i$ 行目には $i$ 番目のクエリの答えを出力してください。最後に改行してください。

    サンプル

    サンプル1
    入力
    3 5
    2 1
    1 3
    3 1 2
    2 1 1
    1 3 3
    1 3 1
    1 1 1
    
    出力
    0
    1
    7
    0
    3
    

    1クエリ目では $S = \{3\}, X = \{\}$ となっています。$(a, b) (a < b)$となる組は作れないので$0$を出力します。

    2クエリ目では $S = \{2, 3\}, X = \{2, 3\}$ となっています。 $\mathrm {LCA}_T (1, 2, 3) = 1$ なので$1$を出力します。

    3クエリ目では $S = \{1, 2, 3\}, X = \{1, 2, 3\}$ となっています。 $\mathrm {LCA}_T (3, 1, 2) = 1, \mathrm {LCA}_T (3, 1, 3) = 3, \mathrm {LCA}_T (3, 2, 3) = 3$ なのでその和である$7$を出力します。

    4クエリ目では $S = \{2, 3\}, X = \{2\}$ となっています。$(a, b) (a < b)$となる組は作れないので$0$を出力します。

    5クエリ目では $S = \{1, 2, 3\}, X = \{1, 2, 3\}$ となっています。$\mathrm {LCA}_T (1, 1, 2) = 1, \mathrm {LCA}_T (1, 1, 3) = 1, \mathrm {LCA}_T (1, 2, 3) = 1$ なのでその和である$3$を出力します。

    サンプル2
    入力
    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
    
    出力
    0
    5
    14
    2
    7
    2
    35
    29
    7
    2
    0
    2
    2
    

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。