問題一覧 > 通常問題

No.2163 LCA Sum Query

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : akakimidoriakakimidori / テスター : hotman78hotman78
2 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もしくは右上の雲マークをクリックしてアカウントを作成してください。