結果
問題 | No.2337 Equidistant |
ユーザー | FromBooska |
提出日時 | 2023-10-11 15:17:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,087 ms / 4,000 ms |
コード長 | 3,715 bytes |
コンパイル時間 | 362 ms |
コンパイル使用メモリ | 86,704 KB |
実行使用メモリ | 176,356 KB |
最終ジャッジ日時 | 2023-10-11 15:18:14 |
合計ジャッジ時間 | 33,265 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 91 ms
71,448 KB |
testcase_01 | AC | 93 ms
71,624 KB |
testcase_02 | AC | 96 ms
71,712 KB |
testcase_03 | AC | 93 ms
71,576 KB |
testcase_04 | AC | 97 ms
71,400 KB |
testcase_05 | AC | 94 ms
71,300 KB |
testcase_06 | AC | 216 ms
80,756 KB |
testcase_07 | AC | 218 ms
80,428 KB |
testcase_08 | AC | 215 ms
80,800 KB |
testcase_09 | AC | 222 ms
81,124 KB |
testcase_10 | AC | 222 ms
80,236 KB |
testcase_11 | AC | 1,512 ms
152,688 KB |
testcase_12 | AC | 1,485 ms
152,956 KB |
testcase_13 | AC | 1,565 ms
153,376 KB |
testcase_14 | AC | 1,589 ms
152,512 KB |
testcase_15 | AC | 1,596 ms
152,596 KB |
testcase_16 | AC | 1,537 ms
152,812 KB |
testcase_17 | AC | 1,465 ms
152,700 KB |
testcase_18 | AC | 1,505 ms
152,796 KB |
testcase_19 | AC | 1,562 ms
152,608 KB |
testcase_20 | AC | 1,581 ms
153,060 KB |
testcase_21 | AC | 1,504 ms
148,868 KB |
testcase_22 | AC | 1,231 ms
176,356 KB |
testcase_23 | AC | 1,463 ms
157,540 KB |
testcase_24 | AC | 1,964 ms
148,936 KB |
testcase_25 | AC | 1,419 ms
157,820 KB |
testcase_26 | AC | 2,087 ms
149,136 KB |
testcase_27 | AC | 1,531 ms
158,052 KB |
testcase_28 | AC | 1,481 ms
157,316 KB |
ソースコード
# ルート決めてLCA # 2頂点のdepthが同じなら、LCAおよびその親、その先すべて # 2頂点のdepthが異なり、そのdepth diffが奇数なら0 # 偶数なら1でいいか ## library of LCA by class ## index start from 0 import sys sys.setrecursionlimit(10**7) from collections import deque class LCA: def __init__(self,n): self.size = n self.bitlen = n.bit_length() self.ancestor = [[0]*self.size for i in range(self.bitlen)] self.depth = [-1]*self.size self.dis = [-1]*self.size ## using [log_n][n] [n][log_n] ## [log_n][n] is tend to faster than [n][log_n] ## get parent by bfs is probably faster than dfs def make(self,root): self.depth[root] = 0 self.dis[root] = 0 q = deque([root]) while q: now = q.popleft() for nex in edges[now]: if self.depth[nex]>= 0: continue self.depth[nex] = self.depth[now]+1 self.dis[nex] = self.dis[now]+1 self.ancestor[0][nex] = now q.append(nex) for i in range(1,self.bitlen): for j in range(self.size): if self.ancestor[i-1][j] > 0: self.ancestor[i][j] = self.ancestor[i-1][self.ancestor[i-1][j]] def lca(self,x,y): dx = self.depth[x] dy = self.depth[y] if dx < dy: x,y = y,x dx,dy = dy,dx dif = dx-dy while dif: s = dif & (-dif) x = self.ancestor[s.bit_length()-1][x] dif -= s while x != y: j = 0 while self.ancestor[j][x] != self.ancestor[j][y]: j += 1 if j == 0: return self.ancestor[0][x] x = self.ancestor[j-1][x] y = self.ancestor[j-1][y] return x def par(self,x,dep): #親parent now = x for i in range(self.bitlen)[::-1]: if 1 << i <= dep: now = self.ancestor[i][now] dep -= 1<<i return now N, Q = map(int, input().split()) edges = [[] for i in range(N+1)] for i in range(N-1): a, b = map(int, input().split()) edges[a].append(b) edges[b].append(a) lca = LCA(N+1) # 頂点数 lca.make(1) # ルート # 部分木、子の数を数える # dfsだとMLE, python3だとTLE # なのでこの方のque方法にする root = 1 child = [0]*(N+1) visited = [0]*(N+1) que = [root] visited[root] = 1 topological = [] parent = [-1]*(N+1) while que: current = que.pop() topological.append(current) for nxt in edges[current]: if visited[nxt] == 0: parent[nxt] = current visited[nxt] = 1 que.append(nxt) for current in topological[::-1]: count = 1 for nxt in edges[current]: if nxt != parent[current]: count += child[nxt] child[current] = count #print(child) for q in range(Q): s, t = map(int, input().split()) if lca.depth[s] < lca.depth[t]: s, t = t, s p = lca.lca(s, t) distance_st = lca.depth[s]+lca.depth[t]-lca.depth[p]*2 if distance_st%2 == 1: ans = 0 print(ans) continue center = lca.par(s, distance_st//2) #print('center', center) # distance_stの半分だけ上に上がった頂点 if lca.depth[s] != lca.depth[t]: ans = child[center]-child[lca.par(s, distance_st//2-1)] else: # ans = N-child[center]+1は間違い、枝分かれが3本以上もありうる ans = N-child[lca.par(s, distance_st//2-1)]-child[lca.par(t, distance_st//2-1)] print(ans)