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.



Sample input:
5
0 1
0 2
0 3
3 4


Sample output:
2

Submission status: Accepted

Solution code:
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
    # Req = [True]*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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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
# MOD = 998244353

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

# plot_graph(AB)

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: 枝分かれしてる頂点が先祖にあるか
    """
    # 枝分かれしてる頂点 (次数が3以上の頂点) について、
    # 枝分かれしてる頂点がない方向が1以下になるようにする
    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)
# if ans != test():
#     print(ans, test())
#     print(AB)
#     print()

Submission status: Accepted

Solution code:
#設定
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()

#val = 0

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

	#DFS
	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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# 大混乱したので乱択  # これ嘘じゃないのか？？？

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)

    #for i in range(N):
    #    print(dfs(i, -1, i))

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

main()

Submission status: Accepted

Solution code:
# 大混乱したので乱択

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)

    #for i in range(N):
    #    print(dfs(i, -1, i))

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

main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Runtime Error

Solution code:
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


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)]
for _ in range(n-1):
    a,b=LI()
    G[a]+=[b]
    G[b]+=[a]

visited=[0]*n
visited[0]=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

ans=f(0)
if len(G[0]) == 1:
    ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
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


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)]
for _ in range(n-1):
    a,b=LI()
    G[a]+=[b]
    G[b]+=[a]

visited=[0]*n
a=[0]*n
visited[0]=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
    a[x]=ret
    return ret

ans=f(0)
if len(G[0]) == 1:
    ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
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


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)]
for _ in range(n-1):
    a,b=LI()
    G[a]+=[b]
    G[b]+=[a]

visited=[0]*n
a=[0]*n
visited[0]=1
print(G[2])
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
    a[x]=ret
    return ret

ans=f(0)
if len(G[0]) == 1:
    ans+=1
    
print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
int n,f,t,i,r;
vector<int> g[1<<18];
int dfs(int v, int p) {
	int c0 = 0, a = 0;
	for(int i : g[v]) if(i != p) {
		t = dfs(i, v);
		t ? a += t : ++c0;
	}
	return a + c0 - (c0>0);
}
int main() {
	for(i=(cin>>n,n);--i;) {
		cin>>f>>t;
		g[f].push_back(t);
		g[t].push_back(f);
	}
	while(g[r].size()<3) r++;
	cout << dfs(r, r);
	return 0;
}

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:

"""
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継続

簡単な木では最適になることを実験したがどうだろうか…？
"""

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)

Submission status: Runtime Error

Solution code:
#設定
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()

#val = 0

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()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	if N == 2:
		print(1)
		return

	#DFS
	anstenna = [0] * (N + 1)
	have = [0] * (N + 1)
	edge_num = [len(G.graph[i]) - 1 for i in range(N + 1)]
	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()

Submission status: Runtime Error

Solution code:
def dps(v, p, links):
    lv = links[v]
    if not lv:
        return 0
    cnt0 = 0
    ret = 0
    for l in lv:
        if l == p:
            continue
        res = dps(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) > 1:
            return dps(i, None, links)


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))