結果
問題 | No.2337 Equidistant |
ユーザー | ニックネーム |
提出日時 | 2023-06-02 22:19:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,475 ms / 4,000 ms |
コード長 | 1,836 bytes |
コンパイル時間 | 303 ms |
コンパイル使用メモリ | 87,260 KB |
実行使用メモリ | 148,544 KB |
最終ジャッジ日時 | 2023-08-28 04:05:45 |
合計ジャッジ時間 | 36,828 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 84 ms
71,436 KB |
testcase_01 | AC | 89 ms
71,788 KB |
testcase_02 | AC | 92 ms
71,708 KB |
testcase_03 | AC | 88 ms
71,728 KB |
testcase_04 | AC | 89 ms
71,728 KB |
testcase_05 | AC | 90 ms
71,716 KB |
testcase_06 | AC | 235 ms
81,092 KB |
testcase_07 | AC | 221 ms
81,004 KB |
testcase_08 | AC | 235 ms
81,536 KB |
testcase_09 | AC | 230 ms
80,940 KB |
testcase_10 | AC | 227 ms
80,944 KB |
testcase_11 | AC | 1,807 ms
128,988 KB |
testcase_12 | AC | 1,789 ms
125,432 KB |
testcase_13 | AC | 1,741 ms
124,736 KB |
testcase_14 | AC | 1,748 ms
129,324 KB |
testcase_15 | AC | 1,765 ms
125,968 KB |
testcase_16 | AC | 1,818 ms
124,844 KB |
testcase_17 | AC | 1,715 ms
129,280 KB |
testcase_18 | AC | 1,737 ms
129,408 KB |
testcase_19 | AC | 1,784 ms
124,436 KB |
testcase_20 | AC | 1,777 ms
126,648 KB |
testcase_21 | AC | 1,932 ms
148,336 KB |
testcase_22 | AC | 1,112 ms
133,728 KB |
testcase_23 | AC | 1,539 ms
123,924 KB |
testcase_24 | AC | 2,475 ms
148,544 KB |
testcase_25 | AC | 1,542 ms
133,356 KB |
testcase_26 | AC | 2,373 ms
148,044 KB |
testcase_27 | AC | 1,501 ms
125,712 KB |
testcase_28 | AC | 1,509 ms
126,564 KB |
ソースコード
class DoublingLCA: def __init__(self,n,adj,root=0): self.ancestor,self.depth = [[-1]*(n+1)],[-1]*n stack = [(root,-1,0)] while stack: v,p,dep = stack.pop() self.ancestor[0][v],self.depth[v] = p,dep for c in adj[v]: if c!=p: stack.append((c,v,dep+1)) for _ in range(max(self.depth).bit_length()-1): self.ancestor.append([self.ancestor[-1][v] for v in self.ancestor[-1]]) def get_kth_ancestor(self,v,k): for i in range(k.bit_length()): if k>>i&1: v = self.ancestor[i][v] return v def get_lca(self,u,v): depu,depv = self.depth[u],self.depth[v] if depu>depv: u,v,depu,depv = v,u,depv,depu v = self.get_kth_ancestor(v,depv-depu) if u==v: return u for k in range(depu.bit_length()-1,-1,-1): nu,nv = self.ancestor[k][u],self.ancestor[k][v] if nu!=nv: u,v = nu,nv return self.ancestor[0][u] from collections import deque n,q = map(int,input().split()) adj = [[] for _ in range(n)] for _ in range(n-1): a,b = map(int,input().split()) adj[a-1].append(b-1); adj[b-1].append(a-1) lca = DoublingLCA(n,adj) dq = deque([0]); topo = []; par = [-1]*n while dq: p = dq.popleft(); topo.append(p) for c in adj[p]: if c!=par[p]: dq.append(c); par[c] = p dp = [1]*n for v in topo[::-1]: for c in adj[v]: if c!=par[v]: dp[v] += dp[c] for _ in range(q): s,t = map(int,input().split()); s -= 1; t -= 1 x = lca.depth[s]; y = lca.depth[t] if x<y: s,t,x,y = t,s,y,x d = x+y-2*lca.depth[lca.get_lca(s,t)] a = lca.get_kth_ancestor(s,d//2) b = lca.get_kth_ancestor(s,d//2-1) c = lca.get_kth_ancestor(t,d//2-1) if d%2: print(0) elif x!=y: print(dp[a]-dp[b]) else: print(n-dp[b]-dp[c])