No.2163 LCA Sum Query
タグ : / 解いたユーザー数 13
作問者 : akakimidori / テスター : hotman78
問題文
$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$
出力
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。