結果
問題 | No.1928 Make a Binary Tree |
ユーザー |
![]() |
提出日時 | 2022-05-06 22:25:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 873 ms / 3,000 ms |
コード長 | 2,064 bytes |
コンパイル時間 | 280 ms |
コンパイル使用メモリ | 82,504 KB |
実行使用メモリ | 161,124 KB |
最終ジャッジ日時 | 2024-07-05 23:44:04 |
合計ジャッジ時間 | 26,953 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
import sys input = sys.stdin.readline class SegmentTree: def __init__(self, size, op, identity): n = 1 << (size - 1).bit_length() self.size = n self.op = op self.identity = identity self.node = [identity] * (2 * n) def __getitem__(self, k): return self.node[k + self.size] def build(self, v): for k in range(len(v)): self.node[k + self.size] = v[k] for k in range(self.size - 1, 0, -1): self.node[k] = self.op(self.node[2 * k], self.node[2 * k + 1]) def update(self, k, x): k += self.size self.node[k] = x while k > 1: k >>= 1 self.node[k] = self.op(self.node[2 * k], self.node[2 * k + 1]) def fold(self, l, r): vl = vr = self.identity l += self.size r += self.size while l < r: if l & 1: vl = self.op(vl, self.node[l]) l += 1 if r & 1: r -= 1 vr = self.op(self.node[r], vr) l >>= 1 r >>= 1 return self.op(vl, vr) def euler_tour(G, root): N = len(G) stack = [(root, -1, 1), (root, -1, 0)] et = [] first = [-1] * N last = [-1] * N k = 0 while stack: v, p, t = stack.pop() if t == 0: et.append(v) first[v] = k k += 1 for c in G[v]: if c != p: stack.append((c, v, 1)) stack.append((c, v, 0)) else: last[v] = k return et, first, last N = int(input()) G = [[] for _ in range(N)] for _ in range(N-1): x, y = map(lambda x: int(x)-1, input().split()) G[x].append(y) G[y].append(x) et, first, last = euler_tour(G, 0) st = SegmentTree(N, max, (0, -1)) for v in et[::-1]: m = 1 for _ in range(2): x, i = st.fold(first[v], last[v]) if i != -1: m += x st.update(i, (0, -1)) st.update(first[v], (m, first[v])) print(st[0][0])