from dataclasses import dataclass
from typing import List, Callable, TypeVar
T = TypeVar('T')
U = TypeVar('U')
@dataclass
class RerootingEdge:
src: int
tgt: int
value: U
class Rerooting:
"""
抽象化 全方位木DP
・r = 1,2,...,N について、頂点 r を根とした木DPの結果(DP[r])を求める。
・merge 演算に逆演算が成り立たない場合に対応
・頂点に対して値が決められている場合、辺に対して値が決められている場合(あるいは両方)のいずれにも対応
【使い方】
① __init__()に示された関数を定義する
② add_edge()にてN-1本の辺を与える。u→v と v→u で2回呼んで双方向で与える。
③ solve()
【apply, merge 関数で処理すべき内容】
(u) ans[v] には、"v 自身の値は未反映の" v 以下の部分木に対するDP結果が入る。(その方が定義する関数の数を減らせるため)
/|\ (※ たとえば「ans[i] = i 以下の部分木の頂点数」とした場合、ans[v] には v 自身は加算されていない)
(v)(w)(x) ans[u] を求める際に呼ばれる apply(ans[v]) 内で、v についての情報を加算する。
apply では↑と同時に、辺をv→uとたどる際に何らかの処理が行われる場合はそれも反映する。頂点 u の値の反映は行わない。
merge は、[ unit, apply(ans[v]), apply(ans[w]), apply(ans[x]) ] を左から2つずつ累積的に合成していく処理を行う。
全てマージされた結果が、ans[u] となる。
"""
def __init__(self,
n: int,
leaf_factory: Callable[[], T], # 1回目のDFSで葉に適用する値
unit_factory: Callable[[], T], # 単位元
merge: Callable[[T, T], T], # 演算
apply: Callable[[T, RerootingEdge], T], # [子の値, 親→子への辺] から、親に伝える情報を計算
) -> None:
self.n: int = n
self.links: List[List[RerootingEdge]] = [[] for _ in range(n)]
self.leaf = leaf_factory
self.unit = unit_factory
self.merge = merge
self.apply = apply
def add_edge(self, s, t, value) -> None:
self.links[s].append(RerootingEdge(src=s, tgt=t, value=value))
def solve(self) -> List[T]:
links = self.links
status = [0] * self.n
leaf = self.leaf
unit = self.unit
merge = self.merge
apply = self.apply
# 1回目のDFSで、自身の子のapply済み結果の左からの累積和
acc_left: List[List[T]] = [[unit()] for _ in range(self.n)]
# 1回目のDFSで、自身の子のapply済み結果の右からの累積和
acc_right: List[List[T]] = [[unit()] for _ in range(self.n)]
# 最終結果(1回目のDFSでは自身のsubtreeのみの結果が入る)
ans: List[T] = [unit() for _ in range(self.n)]
# 親に向かう辺
parents: List[RerootingEdge | None] = [None for _ in range(self.n)]
# 2回目のDFSで、親から伝播される値(apply済)
from_parent: List[T] = [unit() for _ in range(self.n)]
q = [0]
while q:
v = q[-1]
if status[v] == 0:
status[v] = 1
# 親頂点をリンクリストから除く
children_links = []
for e in links[v]:
if status[e.tgt] == 0:
children_links.append(e)
else:
parents[v] = e
links[v] = children_links
for e in links[v]:
q.append(e.tgt)
else:
q.pop()
if len(links[v]) == 0:
ans[v] = leaf()
else:
acl = acc_left[v]
for e in links[v]:
acl.append(apply(ans[e.tgt], e))
acr = acc_right[v]
for i in range(len(acl) - 1, 0, -1):
acr.append(merge(acl[i], acr[-1]))
acr.reverse()
for i in range(1, len(acl)):
acl[i] = merge(acl[i - 1], acl[i])
ans[v] = acl[-1]
status[v] = 2
q = [0]
while q:
v = q.pop()
fp = from_parent[v]
ans[v] = merge(ans[v], fp)
acl = acc_left[v]
acr = acc_right[v]
for li, e in enumerate(links[v]):
pe = parents[e.tgt]
tgt_data = merge(fp, merge(acl[li], acr[li + 1]))
from_parent[e.tgt] = apply(tgt_data, pe)
q.append(e.tgt)
return ans
n = int(input())
# 1: その部分木内でゲートを使った場合の最小コスト
# 2: 部分木の頂点数(v そのものの頂点の +1 は未反映)
# 3: 部分木の最大深さ(v そのものの深さの +1 は未反映)
# 4: 最後に訪れる枝として選ぶときの、1 から省略できるコスト差分
leaf_factory = lambda: (0, 0, 0, 0)
unit_factory = lambda: (0, 0, 0, 0)
def merge(a, b):
a1, a2, a3, a4 = a
b1, b2, b3, b4 = b
return (a1 + b1, a2 + b2, max(a3, b3), max(a4, b4))
def apply(p, e):
p1, p2, p3, p4 = p
p2 += 1
p3 += 1
best_cost = min(p1 + 2, p2 * 2 - p3)
last_cost = min(p1 - p4 + 1, p2 * 2 - p3)
return (best_cost, p2, p3, best_cost - last_cost)
rrt = Rerooting(n, leaf_factory, unit_factory, merge, apply)
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
rrt.add_edge(u, v, 0)
rrt.add_edge(v, u, 0)
result = rrt.solve()
ans = 1 << 60
for p1, _, _, p4 in result:
ans = min(ans, p1 - p4)
print(ans)