結果
問題 | No.399 動的な領主 |
ユーザー | 👑 rin204 |
提出日時 | 2022-09-30 23:07:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 700 ms / 2,000 ms |
コード長 | 2,345 bytes |
コンパイル時間 | 1,832 ms |
コンパイル使用メモリ | 86,672 KB |
実行使用メモリ | 115,616 KB |
最終ジャッジ日時 | 2023-08-24 16:42:03 |
合計ジャッジ時間 | 12,358 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 80 ms
71,252 KB |
testcase_01 | AC | 80 ms
70,788 KB |
testcase_02 | AC | 82 ms
71,168 KB |
testcase_03 | AC | 84 ms
71,064 KB |
testcase_04 | AC | 196 ms
77,572 KB |
testcase_05 | AC | 229 ms
81,176 KB |
testcase_06 | AC | 685 ms
112,996 KB |
testcase_07 | AC | 669 ms
113,820 KB |
testcase_08 | AC | 666 ms
113,728 KB |
testcase_09 | AC | 631 ms
113,396 KB |
testcase_10 | AC | 149 ms
78,324 KB |
testcase_11 | AC | 208 ms
81,348 KB |
testcase_12 | AC | 571 ms
115,616 KB |
testcase_13 | AC | 607 ms
114,744 KB |
testcase_14 | AC | 339 ms
113,284 KB |
testcase_15 | AC | 346 ms
113,320 KB |
testcase_16 | AC | 392 ms
112,944 KB |
testcase_17 | AC | 700 ms
113,448 KB |
testcase_18 | AC | 678 ms
113,640 KB |
ソースコード
class LCA: def __init__(self, G, root=0): self.G = G self.root = root self.n = len(G) self.logn = (self.n - 1).bit_length() self.depth = [-1 if i != root else 0 for i in range(self.n)] self.parent = [[-1] * self.n for _ in range(self.logn)] self.dfs() self.doubling() def dfs(self): que = [self.root] while que: u = que.pop() for v in self.G[u]: if self.depth[v] == -1: self.depth[v] = self.depth[u] + 1 self.parent[0][v] = u que += [v] def doubling(self): for i in range(1, self.logn): for v in range(self.n): if self.parent[i - 1][v] != -1: self.parent[i][v] = self.parent[i - 1][self.parent[i - 1][v]] def get(self, u, v): if self.depth[v] < self.depth[u]: u, v = v, u du = self.depth[u] dv = self.depth[v] for i in range(self.logn): if (dv - du) >> i & 1: v = self.parent[i][v] if u == v: return u for i in range(self.logn - 1, -1, -1): pu, pv = self.parent[i][u], self.parent[i][v] if pu != pv: u, v = pu, pv return self.parent[0][u] def dist(self, u, v): return self.depth[u] + self.depth[v] - 2 * self.depth[self.get(u, v)] n = int(input()) edges = [[] for _ in range(n + 1)] for _ in range(n - 1): u, v = map(int, input().split()) edges[u].append(v) edges[v].append(u) edges[0].append(1) edges[1].append(0) lca = LCA(edges) imos = [0] * (n + 1) Q = int(input()) for _ in range(Q): a, b = map(int, input().split()) p = lca.get(a, b) imos[b] += 1 imos[a] += 1 imos[p] -= 1 imos[lca.parent[0][p]] -= 1 route = [0] stack = [0] used = [False] * (n + 1) used[0] = True while stack: pos = stack.pop() for npos in edges[pos]: if used[npos]: continue used[npos] = True stack.append(npos) route.append(npos) used = [False] * (n + 1) for pos in route[::-1]: used[pos] = True for npos in edges[pos]: if not used[npos]: continue imos[pos] += imos[npos] ans = 0 for i in imos: ans += i * (i + 1) // 2 print(ans)