Problem:
 Score : 900 points    Problem Statement We have a tree with N vertices.
The vertices are numbered 0 through N - 1 , and the i -th edge ( 0 ≤ i < N - 1 ) comnnects Vertex a_i and b_i .
For each pair of vertices u and v ( 0 ≤ u, v < N ), we define the distance d(u, v) as the number of edges in the path u - v .  It is expected that one of the vertices will be invaded by aliens from outer space.
Snuke wants to immediately identify that vertex when the invasion happens.
To do so, he has decided to install an antenna on some vertices.  First, he decides the number of antennas, K ( 1 ≤ K ≤ N ).
Then, he chooses K different vertices, x_0 , x_1 , ..., x_{K - 1} , on which he installs Antenna 0 , 1 , ..., K - 1 , respectively.
If Vertex v is invaded by aliens, Antenna k ( 0 ≤ k < K ) will output the distance d(x_k, v) .
Based on these K outputs, Snuke will identify the vertex that is invaded.
Thus, in order to identify the invaded vertex no matter which one is invaded, the following condition must hold:   For each vertex u ( 0 ≤ u < N ), consider the vector (d(x_0, u), ..., d(x_{K - 1}, u)) . These N vectors are distinct.   Find the minumum value of K , the number of antennas, when the condition is satisfied.      Constraints  2 ≤ N ≤ 10^5  0 ≤ a_i, b_i < N  The given graph is a tree.         Input Input is given from Standard Input in the following format:  N  a_0  b_0  a_1  b_1  :  a_{N - 2}  b_{N - 2}       Output Print the minumum value of K , the number of antennas, when the condition is satisfied.        Sample Input 1 5
0 1
0 2
0 3
3 4      Sample Output 1 2  For example, install an antenna on Vertex 1 and 3 .
Then, the following five vectors are distinct:   (d(1, 0), d(3, 0)) = (1, 1)  (d(1, 1), d(3, 1)) = (0, 2)  (d(1, 2), d(3, 2)) = (2, 2)  (d(1, 3), d(3, 3)) = (2, 0)  (d(1, 4), d(3, 4)) = (3, 1)        Sample Input 2 2
0 1      Sample Output 2 1  For example, install an antenna on Vertex 0 .       Sample Input 3 10
2 8
6 0
4 1
7 6
2 3
8 6
6 9
2 4
5 8      Sample Output 3 3  For example, install an antenna on Vertex 0 , 4 , 9 .

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20
sys.setrecursionlimit(2147483647)

def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n=I()
G=[[]for _ in range(n)]
r=-1
for _ in range(n-1):
    a,b=LI()
    G[a]+=[b]
    G[b]+=[a]
    if len(G[a])>2:
        r=a
    if len(G[b]) > 2:
        r=b

visited=[0]*n
visited[r]=1
def f(x):
    ret=0
    cnt=0
    for v in G[x]:
        if visited[v]:
            continue
        visited[v] = 1
        r=f(v)
        ret+=r
        if r==0:
            cnt+=1
    if cnt>1:
        ret+=cnt-1
    return ret

print(1 if r == -1 else f(r))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)


dp = [1] * N

def dfs(v, p):
    cnt = 0
    for c in G[v]:
        if c == p:
            continue
        dfs(c, v)
        if dp[c] == 1:
            cnt += 1
        dp[v] += dp[c] - 1
    if cnt > 1:
        dp[v] += cnt - 1

dfs(0, -1)

ans = [1] * N

def dfs2(v, p, par_val):
    cnt = 0
    for c in G[v]:
        if c == p:
            continue
        if dp[c] == 1:
            cnt += 1
        ans[v] += dp[c] - 1
    if p != -1:
        if par_val == 1:
            cnt += 1
        ans[v] += par_val - 1
    if cnt > 1:
        ans[v] += cnt - 1
    for c in G[v]:
        if c == p:
            continue
        dfs2(c, v, ans[v] - (dp[c] - 1) - (1 if dp[c] == 1 and cnt > 1 else 0))

dfs2(0, -1, 0)
print(min(ans))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
ab = list(map(int,read().split()))

links = [[] for _ in range(n)]
it = iter(ab)
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

root = 0
parent = [-2] * n
parent[root] = -1
ts = [root]
stack = [root]
while(stack):
    next = []
    while(stack):
        i = stack.pop()
        for j in links[i]:
            if(parent[j] != -2):
                continue
            ts.append(j)
            next.append(j)
            parent[j] = i
    stack = next[::]

root = ts[-1]
parent = [-2] * n
parent[root] = -1
ts = [root]
stack = [root]
while(stack):
    next = []
    while(stack):
        i = stack.pop()
        for j in links[i]:
            if(parent[j] != -2):
                continue
            ts.append(j)
            next.append(j)
            parent[j] = i
    stack = next[::]

ts = ts[::-1]
nums = [0] * n
for i in ts:
    cnt_0 = 0
    for j in links[i]:
        if(j == parent[i]):
            continue
        if(nums[j] == 0):
            cnt_0 += 1
        else:
            nums[i] += nums[j]
    nums[i] += max(0,cnt_0-1)

ans = nums[root]
if(len(links[root])==1):
    ans += 1

print(ans)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for i in range(n)]
    for _ in [0]*(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)
    rt = -1
    for i in range(n):
        if len(way[i]) > 2:
            rt = i
            break

    def dp(pp,np):
        sum = 0
        n0 = 0
        for i in way[np]:
            if i == pp:
                continue
            tmp = dp(np,i)
            sum += tmp
            if tmp == 0:
                n0 += 1
        if n0 > 1:
            sum += n0-1
        return sum

    if rt == -1:
        print(1)
        exit()
    else:
        print(dp(-1,rt))

    return

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a].append(b) for a, b in ab]
    [g[b].append(a) for a, b in ab]
    for i in range(n):
        if len(g[i]) > 2:
            root = i
            break
    else:
        print(1)
        return
    d = [-1]*n  
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d2 = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    stock = [0]*n
    ans = 0
    for _, i in d2:
        dist = d[i]
        s = 0
        cnt = 0
        for j in g[i]:
            if dist < d[j]:
                s += stock[j]
                cnt += 1
        ans += max(cnt-s-1, 0)
        s += max(cnt-s-1, 0)
        if s > 0 or cnt > 1:
            stock[i] = 1
    print(ans)


main()

Solution (Python):
import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

antena=[]
for i in range(N):
    if len(edge[i])>2:
        antena.append(i)

if not antena:
    print(1)
    exit()

parent=[-1]*N
root=antena[0]

def dfs(v,pv):
    parent[v]=pv
    for i in edge[v]:
        if i!=pv:
            dfs(i,v)

dfs(root,-1)

antena=set(antena)

q=[root]
sub=[]
while q:
    while q:
        x=q.pop()
        if x in antena:
            v=x
            while parent[v] not in antena and parent[v]!=-1:
                antena.add(parent[v])
                v=parent[v]
        for nv in edge[x]:
            if nv!=parent[x]:
                sub.append(nv)

        if not q:
            q=sub
            sub=[]
            break

ans=0
for u in antena:
    if len(edge[u])==1:
        ans+=1
    elif len(edge[u])==2:
        check=0
        for v in edge[u]:
            check+=(v in antena)
        if check==1:
            ans+=1
    else:
        check=0
        for v in edge[u]:
            check+=(v in antena)
        if check>=len(edge[u])-1:
            continue
        else:
            ans+=len(edge[u])-1-check
print(ans)

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/apc001/tasks/apc001_e

厳密な照明は難しいが…
直径を取る
直径の端点からbfs

全ての頂点に関して、部分木に少なくとも一つのアンテナを持つかのフラグを管理
子の数をkとする。その内x個がtrueの場合、k-1-x個のアンテナを追加。自分のflagをtrueにする
子がfalseで、子が0 or 1つしかない場合のみfalse継続

簡単な木では最適になることを実験したがどうだろうか…？
"""
import sys
sys.setrecursionlimit(3*10**5)

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis,now

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    lis[a].append(b)
    lis[b].append(a)

td,tp,stp = NC_Dij(lis,0)


ans = 0

def dfs(v,p):

    x = 0
    c = 0
    retflag = False
    for nex in lis[v]:

        if nex != p:
            c += 1
            have = dfs(nex,v)
            retflag = have or retflag
            if have:
                x += 1

    if c-1-x > 0:
        retflag = True
    global ans
    ans += max(0,c-1-x)

    return retflag

dfs(stp,stp)
print (ans+1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

s = -1
for n in range(N):
    if len(graph[n]) > 2:
        s = n
        break

checked = [False]*N


def dfs2(s):
    ans = 0
    S = [0]*N
    T = [0]*N
    
    Ind = [0]*N
    stack = [s]
    while stack:
        p = stack[-1]
        if Ind[p] == len(graph[p]):
            ans += max(T[p] - S[p] - 1, 0)
            stack.pop()
            if stack:
                par = stack[-1]
                T[par] += 1
                if S[p] > 0 or T[p] > 1:
                    S[par] += 1
        elif len(stack) > 1 and stack[-2] == graph[p][Ind[p]]:
            Ind[p] += 1
        else:
            stack.append(graph[p][Ind[p]])
            Ind[p] += 1
    return ans


if s == -1:
    ans = 1
else:
    ans = dfs2(s)

print(ans)

Solution (Python):
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ones = list(filter(lambda i:len(g[i])==1,range(n)))
if max([len(g[i]) for i in range(n)]) <= 2:
  print(1)
  exit()
def nbh(i):
  inext = g[i][0]
  def nbh_(xnext,x):
    return g[xnext][0] ^ g[xnext][1] ^ x
  while len(g[inext]) <= 2:
    i,inext = inext,nbh_(inext,i)
  return inext
edges = list(set([nbh(i) for i in ones]))
print(len(ones)-len(edges))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)

leaf = [False for _ in range(n)]

for i in range(n):
	if len(adj[i]) == 1:
		leaf[i] = True

stack = [i for i in range(n) if leaf[i]]
while stack:
	l = stack.pop()
	for v in adj[l]:
		if len(adj[v]) < 3 and not leaf[v]:
			leaf[v] = True
			stack.append(v)

ans = 0
def dfs(x, p):
	global ans
	cnt = 0
	for v in adj[x]:
		if v == p:
			continue
		if leaf[v]:
			cnt += 1
		else:
			dfs(v, x)
	ans += max(0, cnt-1)

if sum(leaf) == n:
	print(1)
else:
	for i in range(n):
		if not leaf[i]:
			root = i
			break
	dfs(root, -1)
	print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
st = -1
for a,b in AB:
    es[a].append(b)
    es[b].append(a)
    if len(es[a]) >= 3: st = a
    if len(es[b]) >= 3: st = b
if st < 0:
    print(1)
    exit()

def rec(v,p=-1):
    ret = 0
    child_anntena = 0
    for to in es[v]:
        if to==p: continue
        tmp = rec(to,v)
        ret += tmp
        if tmp:
            child_anntena += 1
    n = len(es[v]) - 2
    if p<0: n += 1
    ret += max(0, n - child_anntena)
    return ret
print(rec(st))

Solution (Python):
import itertools
import os
import sys

import numpy as np
from scipy.sparse.csgraph._shortest_path import floyd_warshall

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]



graph = [[] for _ in range(N)]

for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)


def test():
    G = [[0] * N for _ in range(N)]
    for a, b in AB:
        G[a][b] = 1
        G[b][a] = 1
    dist = floyd_warshall(G)
    ret = N
    for choice in itertools.product([True, False], repeat=N):
        k = sum(choice)
        if k == 0:
            continue
        if k >= ret:
            continue
        D = dist[np.array(choice, dtype=bool)]
        s = set()
        for d in D.T:
            s.add(str(d))
        if len(s) == D.shape[1]:
            ret = min(ret, k)
    return ret


def dfs(v, p, forked):
    """
    :param v:
    :param p:
    :param bool forked: 枝分かれしてる頂点が先祖にあるか
    """
    
    
    counts = []
    for u in graph[v]:
        if u == p:
            continue
        cnt = dfs(u, v, forked or len(graph[v]) >= 3)
        counts.append(cnt)
    zeros = counts.count(0) + (not forked)
    return sum(counts) + max(0, zeros - 1)


leaf = 0
for v in range(N):
    if len(graph[v]) == 1:
        leaf = v
        break
ans = dfs(leaf, None, False)
print(ans)

Solution (Python):

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)


from collections import defaultdict


def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()



def DFS(G, anstenna, edge_num, have, visit, node):
	cnt = 0
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, anstenna, edge_num, have, visit, i)
			if have[i] == 1:
				cnt += 1
				anstenna[node] += anstenna[i]

	if cnt < edge_num[node] - 1:
		anstenna[node] += edge_num[node] - 1 - cnt
	if anstenna[node] >= 1:
		have[node] = 1


def main():
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		G.add_edge(a, b)
		G.add_edge(b, a)

	if N == 2:
		print(1)
		return

	
	anstenna = [0] * (N + 1)
	have = [0] * (N + 1)
	edge_num = [len(G.graph[i]) - 1 for i in range(N + 1)]

	if max(edge_num) <= 1:
		print(1)
		return

	visit = ["No"] * (N + 1)
	visit[N] = "Yes"
	s = None
	for i in range(N):
		if edge_num[i] >= 1:
			s = i
			break
	G.add_edge(N, s)
	G.add_edge(s, N)
	edge_num[s] += 1

	DFS(G, anstenna, edge_num, have, visit, N)
	ans = anstenna[N]
	if edge_num[s] == 2:
		cnt = 0
		for i in G.graph[s]:
			if have[i] == 1:
				cnt += 1
		if cnt <= 2:
			ans += 1

	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import Counter 
from random import randrange
def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            ast(vf)
    return par, order

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


N = int(readline())
Edge = [[] for _ in range(N)]
Leaf = [0]*N
for _ in range(N-1):
    a, b = map(int, readline().split())
    Leaf[a] += 1
    Leaf[b] += 1
    Edge[a].append(b)
    Edge[b].append(a)

Leaf = [i for i in range(N) if Leaf[i] == 1]
M = len(Leaf)
ANS = 10**9+7 
for idx in [0] + [randrange(1, M) for _ in range(10)]:
    root = Leaf[idx]
    P, L = parorder(Edge, root)
    C = getcld(P)
    
    dp = [0]*N
    countone = [0]*N
    for l in L[::-1][:-1]:
        p = P[l]
        dp[l] += 1 + max(0, countone[l] - 1)
        if dp[l] == 1:
            countone[p] += 1
        dp[p] += dp[l] - 1
        
    dp[root] += 1 + max(0, countone[root] - 1)
    ANS = min(ANS, dp[root])
print(ANS)

Solution (Python):


def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    if N==2:
        print(1)
        exit()
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d = dfs(u, v, root)
                res += d
                cnt_false += d == 0
        return res + max(0, cnt_false - 1)

    
    

    print(max(dfs(i, -1, i) for i in sorted(range(N), key=lambda x: -len(E[x]))[:1]))

main()

Solution (Python):


from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    if N==2:
        print(1)
        exit()
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d = dfs(u, v, root)
                res += d
                cnt_false += d == 0
        return res + max(0, cnt_false - 1)

    
    

    print(max(dfs(i, -1, i) for i in sorted(range(N), key=lambda x: -len(E[x]))[:5]))

main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・次数3以上の点 → d-2個以上の成分に対して1つ以上置かれていないといけない
・それを満たす or 線分 のときに十分：縮約して帰納法
・各部分木に対して、親側にあるとした場合の最小個数を求める
・根として次数3以上の点をとっておけばよい
"""

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a+1].append(b+1)
    graph[b+1].append(a+1)

deg = [len(x) for x in graph]
root = deg.index(max(deg))

if deg[root] <= 2:
    
    print(1)
    exit()

"""
・dp遷移：max(dp[child],1) の和。ただし0を1つまで許容できる。
・0を既に受け入れたかどうかを補助的にもう1つ持つ。
"""

parent = [0] * (N+1)
ts = []
stack = [root]
while stack:
    x = stack.pop()
    ts.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

dp = [0] * (N+1)
use_0 = [False] * (N+1)

for x in ts[::-1]:
    p = parent[x]; d = dp[x]
    if d > 0:
        dp[p] += d
    else:
        if not use_0[p]:
            use_0[p] = True
        else:
            dp[p] += 1

answer = dp[root]
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

leaf = []
for i in range(N):
    if len(adj[i]) == 1:
        leaf.append(i)

if len(leaf) == 2:
    print(1)
    sys.exit()

par = {}
for v in leaf:
    while True:
        v_list = adj[v]
        if len(v_list) == 1:
            v_prev = v
            v = v_list[0]
        else:
            v1, v2 = v_list
            v, v_prev = v1 + v2 - v_prev, v
        if len(adj[v]) > 2:
            par[v] = 0
            break
print(len(leaf) - len(par))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b = LI()
        e[a].append(b)
        e[b].append(a)

    t = -1
    for i in range(n):
        if len(e[i]) > 2:
            t = i
            break
    if t < 0:
        return 1

    def f(i, s):
        c = 0
        t = 0
        for d in e[i]:
            if d == s:
                continue
            r = f(d, i)
            if r == 0:
                c += 1
            else:
                t += r

        if c > 1:
            t += c - 1
        return t

    return f(t, -1)



print(main())

Solution (Python):
import sys

sys.setrecursionlimit(100000)


def dfs(v, p, links):
    lv = links[v]
    if len(lv) == 1:
        return 0
    cnt0 = 0
    ret = 0
    for l in lv:
        if l == p:
            continue
        res = dfs(l, v, links)
        ret += res
        if res == 0:
            cnt0 += 1
    if cnt0:
        ret += cnt0 - 1
    return ret


def solve(n, links):
    if n == 2:
        return 1
    for i, l in enumerate(links):
        if len(l) > 2:
            return dfs(i, None, links)
    else:
        return 1


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    links[a].add(b)
    links[b].add(a)
print(solve(n, links))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)


init = -1
for i in range(N):
    if len(G[i]) >= 3:
        init = i
        break
if init == -1:
    print(1)
    exit(0)

def dfs(v, p):
    res = []
    for w in G[v]:
        if w == p:
            continue
        res.append(dfs(w, v))
    c = len(res)
    if c == 0:
        return 0
    if c == 1:
        return res[0]
    zero = res.count(0)
    if zero >= 2:
        return sum(res) + (zero - 1)
    return sum(res)
print(dfs(init, -1))