結果
問題 | No.2337 Equidistant |
ユーザー | Shirotsume |
提出日時 | 2023-06-02 22:01:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,480 ms / 4,000 ms |
コード長 | 3,588 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 87,212 KB |
実行使用メモリ | 184,180 KB |
最終ジャッジ日時 | 2023-08-28 03:31:02 |
合計ジャッジ時間 | 33,517 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 115 ms
74,188 KB |
testcase_01 | AC | 118 ms
74,488 KB |
testcase_02 | AC | 114 ms
74,152 KB |
testcase_03 | AC | 114 ms
74,448 KB |
testcase_04 | AC | 114 ms
74,052 KB |
testcase_05 | AC | 115 ms
74,332 KB |
testcase_06 | AC | 240 ms
83,848 KB |
testcase_07 | AC | 245 ms
84,416 KB |
testcase_08 | AC | 233 ms
83,908 KB |
testcase_09 | AC | 231 ms
83,820 KB |
testcase_10 | AC | 238 ms
84,340 KB |
testcase_11 | AC | 1,435 ms
170,972 KB |
testcase_12 | AC | 1,759 ms
179,252 KB |
testcase_13 | AC | 1,428 ms
170,540 KB |
testcase_14 | AC | 1,756 ms
173,532 KB |
testcase_15 | AC | 1,398 ms
163,428 KB |
testcase_16 | AC | 1,445 ms
171,072 KB |
testcase_17 | AC | 1,456 ms
171,392 KB |
testcase_18 | AC | 1,428 ms
162,796 KB |
testcase_19 | AC | 1,713 ms
170,544 KB |
testcase_20 | AC | 1,819 ms
184,180 KB |
testcase_21 | AC | 1,336 ms
181,420 KB |
testcase_22 | AC | 829 ms
173,056 KB |
testcase_23 | AC | 1,278 ms
163,896 KB |
testcase_24 | AC | 2,081 ms
183,788 KB |
testcase_25 | AC | 1,254 ms
163,180 KB |
testcase_26 | AC | 2,480 ms
184,128 KB |
testcase_27 | AC | 1,397 ms
166,620 KB |
testcase_28 | AC | 1,379 ms
164,272 KB |
ソースコード
import sys, time, random from collections import deque, Counter, defaultdict input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 63 - 1 mod = 998244353 import sys class LcaDoubling: """ links[v] = { u1, u2, ... } (u:隣接頂点, 親は含まない) というグラフ情報から、ダブリングによるLCAを構築。 任意の2頂点のLCAを取得できるようにする """ def __init__(self, n, links, root=0): self.depths = [-1] * n prev_ancestors = self._init_dfs(n, links, root) self.ancestors = [prev_ancestors] max_depth = max(self.depths) d = 1 while d < max_depth: next_ancestors = [prev_ancestors[p] for p in prev_ancestors] self.ancestors.append(next_ancestors) d <<= 1 prev_ancestors = next_ancestors def _init_dfs(self, n, links, root): q = [root] direct_ancestors = [-1] * (n + 1) # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1 self.depths[root] = 0 while q: u = q.pop() for v in links[u]: if self.depths[v] != -1: continue direct_ancestors[v] = u self.depths[v] = self.depths[u] + 1 links[v].discard(u) q.append(v) return direct_ancestors def get_lca(self, u, v): du, dv = self.depths[u], self.depths[v] if du > dv: u, v = v, u du, dv = dv, du tu = u tv = self.upstream(v, dv - du) if u == tv: return u for k in range(du.bit_length() - 1, -1, -1): mu = self.ancestors[k][tu] mv = self.ancestors[k][tv] if mu != mv: tu = mu tv = mv lca = self.ancestors[0][tu] assert lca == self.ancestors[0][tv] return lca def upstream(self, v, k): i = 0 while k: if k & 1: v = self.ancestors[i][v] k >>= 1 i += 1 return v def jump(self, u: int, v: int, i: int) -> int: """ uからvに向けて進んだパスのi番目(0-indexed)の頂点を得る。パス長が足りない場合は-1 """ c = self.get_lca(u, v) du = self.depths[u] dv = self.depths[v] dc = self.depths[c] path_len = du - dc + dv - dc if path_len < i: return -1 if du - dc >= i: return self.upstream(u, i) return self.upstream(v, path_len - i) n, q = mi() graph = [set() for _ in range(n)] for _ in range(n - 1): u, v = mi() u -= 1; v -= 1 graph[u].add(v) graph[v].add(u) L = LcaDoubling(n, graph) def size_of_subtree(s, t): if L.depths[s] < L.depths[t]: return subt[t] else: return n - subt[s] p = list(range(n)) p.sort(key = lambda x: L.depths[x], reverse=True) subt = [0] * n for v in p: for to in graph[v]: if L.depths[to] > L.depths[v]: subt[v] += subt[to] subt[v] += 1 for _ in range(q): s, t = mi() s -= 1; t -= 1 x = L.get_lca(s, t) l = L.depths[s] + L.depths[t] - 2 * L.depths[x] if l % 2 == 1: print(0) else: u = L.jump(s, t, l // 2) s1 = L.jump(u, s, 1) t1 = L.jump(u, t, 1) ans = n - size_of_subtree(u, s1) - size_of_subtree(u, t1) print(ans)