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:
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(4)]:
    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(dp[root])

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter 

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)

root = Leaf.index(1)
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)
print(dp[root])

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter 

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)

root = Leaf.index(1)
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[0] - 1)
print(dp[0])

Submission status: Wrong Answer

Solution code:
n = int(input())
print(n-2)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

Submission status: Wrong Answer

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

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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)
    #             res += d
    #             cnt_false += d == 0
    #     if root==v:
    #         fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
    #         if fixed_cnt_true <= 1:
    #             res += 1
    #     return res + max(0, cnt_false - 1)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        ok = True
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d, ok_ = dfs(u, v, root)
                ok &= ok_
                res += d
                cnt_false += d == 0
        fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
        #print(cnt_child-cnt_false, max(0, cnt_false - 1))
        if cnt_child == fixed_cnt_true >= 2:
            ok = True
        #print(ok, max(0, cnt_false - 1))
        if cnt_child==0:
            ok = False
        #print(v, ok)
        if root==v and not ok and fixed_cnt_true < 2:
            res += 1
        #print(f"v={v}, ok={ok}, res={res + max(0, cnt_false - 1)}")
        return res + max(0, cnt_false - 1), ok

    print(min(dfs(i, -1, i)[0] for i in [randint(0, N-1) for _ in range(5)]))

main()

Submission status: Wrong Answer

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

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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)
    #             res += d
    #             cnt_false += d == 0
    #     if root==v:
    #         fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
    #         if fixed_cnt_true <= 1:
    #             res += 1
    #     return res + max(0, cnt_false - 1)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        ok = True
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d, ok_ = dfs(u, v, root)
                ok &= ok_
                res += d
                cnt_false += d == 0
        fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
        #print(cnt_child-cnt_false, max(0, cnt_false - 1))
        if cnt_child == fixed_cnt_true >= 2:
            ok = True
        #print(ok, max(0, cnt_false - 1))
        if cnt_child==0:
            ok = False
        #print(v, ok)
        if root==v and not ok and fixed_cnt_true < 2:
            res += 1
        #print(f"v={v}, ok={ok}, res={res + max(0, cnt_false - 1)}")
        return res + max(0, cnt_false - 1), ok

    print(max(dfs(i, -1, i)[0] for i in [randint(0, N-1) for _ in range(5)]))

main()

Submission status: Wrong Answer

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

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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 [randint(0, N-1) for _ in range(5)]))

main()

Submission status: Wrong Answer

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

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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
        if root==v:
            fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
            if fixed_cnt_true <= 1:
                res += 1
        return res + max(0, cnt_false - 1)

    print(min(dfs(i, -1, i) for i in [randint(0, N-1) for _ in range(5)]))

main()

Submission status: Wrong Answer

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

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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
        if root==v:
            fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
            if fixed_cnt_true <= 1:
                res += 1
        return res + max(0, cnt_false - 1)

    print(min(dfs(i, -1, i) for i in [randint(0, N-1)]*8))

main()

Submission status: Wrong Answer

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

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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)
    #             res += d
    #             cnt_false += d == 0
    #     if root==v:
    #         fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
    #         if fixed_cnt_true <= 1:
    #             res += 1
    #     return res + max(0, cnt_false - 1)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        ok = True
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d, ok_ = dfs(u, v, root)
                ok &= ok_
                res += d
                cnt_false += d == 0
        fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
        #print(cnt_child-cnt_false, max(0, cnt_false - 1))
        if cnt_child == fixed_cnt_true >= 2:
            ok = True
        #print(ok, max(0, cnt_false - 1))
        if cnt_child==0:
            ok = False
        #print(v, ok)
        if root==v and not ok and fixed_cnt_true < 2:
            res += 1
        #print(f"v={v}, ok={ok}, res={res + max(0, cnt_false - 1)}")
        return res + max(0, cnt_false - 1), ok

    print(min(dfs(i, -1, i)[0] for i in [randint(0, N-1)]*10))

main()

Submission status: Wrong Answer

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

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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)
    #             res += d
    #             cnt_false += d == 0
    #     if root==v:
    #         fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
    #         if fixed_cnt_true <= 1:
    #             res += 1
    #     return res + max(0, cnt_false - 1)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        ok = True
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d, ok_ = dfs(u, v, root)
                ok &= ok_
                res += d
                cnt_false += d == 0
        fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
        #print(cnt_child-cnt_false, max(0, cnt_false - 1))
        if cnt_child == fixed_cnt_true >= 2:
            ok = True
        #print(ok, max(0, cnt_false - 1))
        if cnt_child==0:
            ok = False
        #print(v, ok)
        if root==v and not ok and fixed_cnt_true < 2:
            res += 1
        #print(f"v={v}, ok={ok}, res={res + max(0, cnt_false - 1)}")
        return res + max(0, cnt_false - 1), ok

    print(max(dfs(i, -1, i)[0] for i in [randint(0, N-1)]*10))

main()

Submission status: Wrong Answer

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

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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)
    #             res += d
    #             cnt_false += d == 0
    #     if root==v:
    #         fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
    #         if fixed_cnt_true <= 1:
    #             res += 1
    #     return res + max(0, cnt_false - 1)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        ok = True
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d, ok_ = dfs(u, v, root)
                ok &= ok_
                res += d
                cnt_false += d == 0
        fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
        #print(cnt_child-cnt_false, max(0, cnt_false - 1))
        if cnt_child == fixed_cnt_true >= 2:
            ok = True
        #print(ok, max(0, cnt_false - 1))
        if cnt_child==0:
            ok = False
        #print(v, ok)
        if root==v and not ok and fixed_cnt_true < 2:
            res += 1
        #print(f"v={v}, ok={ok}, res={res + max(0, cnt_false - 1)}")
        return res + max(0, cnt_false - 1), ok

    print(max(dfs(i, -1, i)[0] for i in [randint(0, N-1)]*3))

main()

Submission status: Wrong Answer

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

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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)
    #             res += d
    #             cnt_false += d == 0
    #     if root==v:
    #         fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
    #         if fixed_cnt_true <= 1:
    #             res += 1
    #     return res + max(0, cnt_false - 1)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        ok = True
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d, ok_ = dfs(u, v, root)
                ok &= ok_
                res += d
                cnt_false += d == 0
        fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
        #print(cnt_child-cnt_false, max(0, cnt_false - 1))
        if cnt_child == fixed_cnt_true >= 2:
            ok = True
        #print(ok, max(0, cnt_false - 1))
        if cnt_child==0:
            ok = False
        #print(v, ok)
        if root==v and not ok and fixed_cnt_true < 2:
            res += 1
        #print(f"v={v}, ok={ok}, res={res + max(0, cnt_false - 1)}")
        return res + max(0, cnt_false - 1), ok

    i = randint(0, N-1)
    print(dfs(i, -1, i)[0])

main()

Submission status: Wrong Answer

Solution code:
# 大混乱

def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    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)
    #             res += d
    #             cnt_false += d == 0
    #     if root==v:
    #         fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
    #         if fixed_cnt_true <= 1:
    #             res += 1
    #     return res + max(0, cnt_false - 1)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        ok = True
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d, ok_ = dfs(u, v, root)
                ok &= ok_
                res += d
                cnt_false += d == 0
        fixed_cnt_true = cnt_child-cnt_false+max(0, cnt_false - 1)
        #print(cnt_child-cnt_false, max(0, cnt_false - 1))
        if cnt_child == fixed_cnt_true >= 2:
            ok = True
        #print(ok, max(0, cnt_false - 1))
        if cnt_child==0:
            ok = False
        #print(v, ok)
        if root==v and not ok and fixed_cnt_true < 2:
            res += 1
        #print(f"v={v}, ok={ok}, res={res + max(0, cnt_false - 1)}")
        return res + max(0, cnt_false - 1), ok

    print(dfs(0, -1, 0)[0])

main()

Submission status: Wrong Answer

Solution code:
from collections import deque
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)

for i in range(N):
    if len(adj[i]) == 1:
        start = i
        break

que = deque()
que.append(start)
seen = [0] * N
div = 0
leaf = 0
while que:
    v = que.pop()
    seen[v] = 1
    adj_num = len(adj[v])
    if adj_num == 1:
        leaf += 1
    elif adj_num > 2:
        div += 1
    for u in adj[v]:
        if seen[u] == 0:
            que.append(u)

if div > 0:
    print(leaf - div)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)
a = len([1 for ee in es if len(ee)==1])
print((a+1)//2)

Submission status: Wrong Answer

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
    flg = False
    ans = 0
    for i, l in enumerate(links):
        if len(l) > 1:
            ans = max(ans, dfs(i, None, links))
            if flg:
                return ans
            flg = True


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

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) > 1:
            return dfs(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))

Submission status: Wrong Answer

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]) == 1:
        init = i
        break

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Accepted

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

Submission status: Accepted

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)


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

Submission status: Accepted

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

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)

Submission status: Accepted

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]
    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:  # 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)
        s += max(cnt-s-1, 0)
        if s > 0 or cnt > 1:
            stock[i] = 1
    print(ans)


main()

Submission status: Accepted

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

簡単な木では最適になることを実験したがどうだろうか…？
"""
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)