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: Wrong Answer

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
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)]
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: Wrong Answer

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

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

for v in range(N):
    if len(G[v]) == 1:
        print(dfs(v, -1))
        break

Submission status: Wrong Answer

Solution code:
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)
deg = [0] * n
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)
    deg[a] += 1
    deg[b] += 1

for i in range(n):
    if(deg[i]==1):
        root = i
        break

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)

print(nums[root] + 1)

Submission status: Wrong Answer

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

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)

Submission status: Wrong Answer

Solution code:
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()))
deg = [0]*n
for i in ab:
    deg[i] += 1

ans = max(deg)-1
print(max(1,ans))

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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):
        if len(way[np]) == 1:
            return [0,1]
        else:
            mi = 10**18
            sum = 0
            f0 = False
            for i in way[np]:
                if i == pp:
                    continue
                else:
                    sti = dp(np,i)
                    if sti[0] == 0:
                        f0 = True
                    sum += sti[1]
                    if sti[1] < mi:
                        mi = sti[1]
            #print(np,sum,mi)
            if f0:
                return [0,sum-mi]
            else:
                return [sum,sum]

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

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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)
    ans = 1
    no3 = 0
    sf = False

    def sym_check(i):
        num = []
        for j in way[i]:
            ni = 0
            pj = j
            while True:
                if len(way[pj]) == 2:
                    ni += 1
                    for k in way[pj]:
                        if not k == pj:
                            pj = k
                            break
                elif len(way[pj]) == 1:
                    ni += 1
                    break
                else:
                    ni = -1
                    break
            num.append(ni)
        if num[0] == num[1] > 0 or num[2] == num[1] > 0 or num[0] == num[2] > 0:
            return True
        else:
            return False

    for i,wi in enumerate(way):
        if len(wi) > 3:
            sf = True
            ans += len(wi)-3
        elif len(wi) == 3:
            sf = True
            if sym_check(i):
                no3 += 1

    if sf:
        ans += 1
    if no3 >= 3:
        ans += (no3-2)

    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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]
    if n == 2:
        print(1)
        return
    else:
        for i in range(n):
            if len(g[i]) == 1:
                root = i
                break
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        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 = 1
    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)
        if s > 0 or cnt > 1:
            stock[i] = 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
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]
    if n == 2:
        print(1)
        return
    else:
        for i in range(n):
            if len(g[i]) > 1:
                root = i
                break
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        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 = 1
    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)
        if s > 0 or cnt > 1:
            stock[i] = 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
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]
    if n == 2:
        print(1)
        return
    else:
        for i in range(n):
            if len(g[i]) > 1:
                root = i
                break
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        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)
        if s > 0 or cnt > 1:
            stock[i] = 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
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]
    if n == 2:
        root = 0
    else:
        for i in range(n):
            if len(g[i]) > 1:
                root = i
                break
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        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)
        if s > 0 or cnt > 1:
            stock[i] = 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
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]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        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
    if len(g[root]) > 1:
        ans = 0
    else:
        ans = 1
    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)
        if s > 0 or cnt > 1:
            stock[i] = 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        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 = 1
    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)
        if s > 0 or cnt > 1:
            stock[i] = 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
for a, b in info:
    tree[a].append(b)
    tree[b].append(a)
    
cnt_leaf = 0
for i in range(n):
    if len(tree[i]) == 1:
        cnt_leaf += 1
print(-((-cnt_leaf) // 2))

Submission status: Wrong Answer

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]) > 1:
        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
            else:
                must = True
                for ch in graph[p]:
                    if len(graph[ch]) == 1:
                        must = False
                        break
                if must: ans += 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: Wrong Answer

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]) > 1:
        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
            else:
                must = True
                for ch in graph[p]:
                    if len(graph[ch]) == 1:
                        must = False
                        break
                if must: ans += 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(0)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
def main():
    N,*E=map(int, open(0).read().split())
    C=Counter(E)
    print((sum(v==1 for v in C.values())+1)//2)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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]) > 1:
        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]):
            if Ind[p] == 1:
                S[p] = 1
            elif Ind[p] > 2:
                S[p] -= 1
            stack.pop()
            if stack:
                par = stack[-1]
                S[par] += S[p]
        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 S[s]


if s == -1:
    ans = 1
else:
    #_, ans = dfs(s, 0)
    ans = dfs2(s)

print(ans)

Submission status: Wrong Answer

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]) > 1:
        s = n
        break

checked = [False]*N
def dfs(p, ans):
    checked[p] = True
    s = 0
    t = 0
    for np in graph[p]:
        if not checked[np]:
            exists, ans = dfs(np, ans)
            t += 1
            if exists:
                s += 1
    if t <= 1: return (s>0), ans
    if s == t: return True, ans
    ans += (t-s)-1
    return True, ans

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 = dfs(s, 0)
    ans = dfs2(s)

print(ans)

Submission status: Wrong Answer

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]) > 1:
        s = n
        break

checked = [False]*N
def dfs(p, ans):
    checked[p] = True
    s = 0
    t = 0
    for np in graph[p]:
        if not checked[np]:
            exists, ans = dfs(np, ans)
            t += 1
            if exists:
                s += 1
    if t <= 1: return (s>0), ans
    if s == t: return True, ans
    ans += (t-s)-1
    return True, ans

def dfs2(s):
    ans = 0
    S = [0]*N
    T = [0]*N
    stack = [s]
    while stack:
        p = stack[-1]
        checked[p] = True
        for np in graph[p]:
            if not checked[np]:
                stack.append(np)
                break
        if stack[-1] != p:
            continue
        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
    return ans


if s == -1:
    ans = 1
else:
    #_, ans = dfs(s, 0)
    ans = dfs2(s)

print(ans)

Submission status: Wrong Answer

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]) > 1:
        s = n
        break

#ans = 0
checked = [False]*N
#D = [False]*N
#D[s] = True
def dfs(p, ans):
    checked[p] = True
    s = 0
    t = 0
    for np in graph[p]:
        if not checked[np]:
            exists, ans = dfs(np, ans)
            #D[np] = exists
            t += 1
            if exists:
                s += 1
    if t <= 1: return (s>0), ans
    if s == t: return True, ans
    ans += (t-s)-1
    return True, ans

if s == -1:
    ans = 1
else:
    _, ans = dfs(s, 0)

print(ans)

Submission status: Wrong Answer

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)

dist = [-1 for _ in range(n)]

def dfs1(x, p):
	for v in adj[x]:
		if dist[v] < 0:
			dist[v] = dist[x] + 1
			dfs1(v, x)

dist[0] = 0
dfs1(0, -1)

max_dist = 0
for i in range(n):
	if dist[i] > max_dist:
		root = i

ans = 0
cnt = 0
par_cnt = 0

def dfs2(x, p):
	global ans, par_cnt
	cnt = 0
	for v in adj[x]:
		if len(adj[v]) == 1:
			cnt += 1
		elif v != p:
			dfs2(v, x)
	ans += max(0, cnt-1)
	if cnt > 1:
		par_cnt += 1

dfs2(root, -1)

if par_cnt < 2:
	ans += 1
print(ans)

Submission status: Wrong Answer

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)

dist = [-1 for _ in range(n)]

def dfs1(x, p):
	for v in adj[x]:
		if dist[v] < 0:
			dist[v] = dist[x] + 1
			dfs1(v, x)

dist[0] = 0
dfs1(0, -1)

max_dist = 0
for i in range(n):
	if dist[i] > max_dist:
		root = i

ans = 1
flg = False
cnt = 0
for v in adj[adj[root][0]]:
	if len(adj[v]) == 1:
		cnt += 1
if cnt == 1:
	flg = True

def dfs2(x, p):
	global ans, flg
	cnt = 0
	for v in adj[x]:
		if v == p:
			continue
		if len(adj[v]) == 1:
			cnt += 1
		else:
			dfs2(v, x)
	ans += max(0, cnt-1)
	if not flg and cnt == 1:
		ans += 1
		flg = True

dfs2(root, -1)
print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    #############################################################
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            self.n = n
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}
    ################################################################################
    N, M = LI()
    a = LI()
    ans = 0
    uf = UnionFind(N)
    for _ in range(M):
        x,y = LI()
        if not uf.same(x,y):
            uf.unite(x,y)
    D = defaultdict(int)
    rep = defaultdict(bool)
    r = uf.roots()
    keep = [-1]*N
    for i in range(N):
        parent = uf.find(i)
        if (not D[parent]) or D[parent] > a[i]:
            D[parent] = a[i]
            keep[parent] = i
    for i in range(N):
        if keep[i]==-1:
            continue
        rep[keep[i]] = True
        ans += D[i]
    loop = uf.group_count()-2
    if loop==-1:
        print(0)
        return
    A = []
    for i,j in enumerate(a):
        A.append([j,i])
    A.sort()
    cur = 0
    for i in range(N):
        if cur>=loop:
            break
        if not rep[A[i][1]]:
            cur +=1
            ans += A[i][0]
    if cur<loop:
        print("Impossible")
        return
    print(ans)
    return

def examE():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        V[a].append(b)
        V[b].append(a)
    L1 = bfs(N,0,V)
    L2 = bfs(N,L1.index(max(L1)),V)
    if max(L2)==N-1:
        print(1)
        return
    ans = 2
    for i in range(N):
        cur = len(V[i])
        if cur>=4:
            ans += cur-3
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

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

# from libs.debug import plot_graph

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):
    # 枝分かれしてる頂点 (次数が3以上の頂点) について、
    # 枝分かれしてる頂点がない方向が1以下になるようにする
    counts = []
    for u in graph[v]:
        if u == p:
            continue
        cnt = dfs(u, v)
        counts.append(cnt)
    zeros = counts.count(0)
    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) + 1
print(ans)
# print(test())

Submission status: Wrong Answer

Solution code:
import os
import sys

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)

# (次数 - 3) の合計 +2
# 枝分かれしてるところを区別するようにするには (次数 - 1) 個のアンテナが必要
# 端っこ 2 つのアンテナは再利用できる
# 葉に置いていけば十分
ans = 0
forked = False
for vs in graph:
    if len(vs) >= 3:
        ans += len(vs) - 3
        forked = True
ans += 2
if forked:
    print(ans)
else:
    print(1)