import sequtils,times template times*(n:int,body) = (for _ in 0.." .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord let n = scan() var E = newSeqWith(n,newSeq[int]()) (n-1).times: let u = scan() - 1 let v = scan() - 1 E[u] &= v E[v] &= u var preHasCutDP = newSeqWith(n,-1) var preHasNotCutDP = newSeqWith(n,-1) var time = 0 proc solve(preHasCut:bool,x:int,preX:int):int = if E[x].len == 0 : return if preHasCut: 1 else: 0 if preHasCut and preHasCutDP[x] != -1 : return preHasCutDP[x] if not preHasCut and preHasNotCutDP[x] != -1 : return preHasNotCutDP[x] time += 1 var whenCut = 0 for e in E[x]: if e != preX : whenCut += solve(true,e,x) var whenNotCut = 0 for e in E[x]: if e != preX : whenNotCut += solve(false,e,x) preHasCutDP[x] = max(whenCut,whenNotCut+1) preHasNotCutDP[x] = max(whenCut,whenNotCut) if preHasCut : whenNotCut += 1 result = max(whenCut,whenNotCut) echo solve(true,0,-1)