結果
問題 | 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 sysinput = sys.stdin.readlineclass SegmentTree:def __init__(self, size, op, identity):n = 1 << (size - 1).bit_length()self.size = nself.op = opself.identity = identityself.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.sizeself.node[k] = xwhile k > 1:k >>= 1self.node[k] = self.op(self.node[2 * k], self.node[2 * k + 1])def fold(self, l, r):vl = vr = self.identityl += self.sizer += self.sizewhile l < r:if l & 1:vl = self.op(vl, self.node[l])l += 1if r & 1:r -= 1vr = self.op(self.node[r], vr)l >>= 1r >>= 1return self.op(vl, vr)def euler_tour(G, root):N = len(G)stack = [(root, -1, 1), (root, -1, 0)]et = []first = [-1] * Nlast = [-1] * Nk = 0while stack:v, p, t = stack.pop()if t == 0:et.append(v)first[v] = kk += 1for c in G[v]:if c != p:stack.append((c, v, 1))stack.append((c, v, 0))else:last[v] = kreturn et, first, lastN = 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 = 1for _ in range(2):x, i = st.fold(first[v], last[v])if i != -1:m += xst.update(i, (0, -1))st.update(first[v], (m, first[v]))print(st[0][0])