Submission #48587355

---

Source Code Expand

import os
import sys
import operator  # noqa
from typing import (IO, Any, Callable, Dict, Iterable, Iterator, List,  # noqa
                    Optional, Set, Tuple, Union)

sys.setrecursionlimit(210000)


if os.getenv('TEST'):
    def eprint(*args, **kwargs):
        print('[EPRINT]', *args, file=sys.stderr, **kwargs)
else:
    def eprint(*args, **kwargs):
        pass


class Node(object):
    def __init__(self) -> None:
        self.count = 0
        self.visited = False
        self.edges: List['Node'] = []


def main() -> None:
    N = int(input())
    nodes = [Node() for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        nodes[a].edges.append(nodes[b])
        nodes[b].edges.append(nodes[a])

    if len(nodes[0].edges) == 1:
        print(1)
        return

    stack: List[Node] = []
    stack.append(nodes[0])
    while len(stack) > 0:
        if not stack[-1].visited:
            stack[-1].visited = True
            for n in stack[-1].edges:
                if not n.visited:
                    stack.append(n)
        else:
            node = stack.pop()
            node.count = 1 + sum(n.count for n in node.edges)

    print(nodes[0].count - max(n.count for n in nodes[0].edges))


if __name__ == '__main__':
    main()

Submission Info

Judge Result