사회망 서비스(SNS)
시간 제한3초메모리 제한256 MB
친구 관계가 트리로 주어질 때, 선택되지 않은 사람의 모든 친구가 선택되도록 하는 최소 얼리어답터 수를 구합니다.
문제
사회망은 그래프로 나타낼 수 있다. 사람은 정점으로, 두 사람의 친구 관계는 두 정점을 잇는 간선으로 표현한다.
새로운 아이디어가 사회망을 통해 퍼질 때, 일부 사람을 초기 수용자로 정할 수 있다. 초기 수용자가 아닌 사람은 자신의 모든 친구가 초기 수용자일 때만 그 아이디어를 받아들인다.
이 문제에서는 친구 관계 그래프가 트리인 경우만 다룬다. 즉, 임의의 두 정점 사이에는 경로가 존재하고 사이클은 없다. 친구 관계 트리가 주어졌을 때, 모든 사람이 아이디어를 받아들이도록 하기 위해 필요한 초기 수용자의 최소 수를 구하시오.
입력
첫째 줄에 친구 관계 트리의 정점 수 N이 주어진다.
2 <= N <= 1,000,000이며, 정점은 1부터 N까지 번호가 붙어 있다.
둘째 줄부터 N - 1개의 줄에는 두 정수 u와 v가 주어진다. 이는 정점 u와 정점 v 사이에 친구 관계 간선이 있음을 의미한다.
출력
주어진 친구 관계 트리에서 모든 사람에게 아이디어를 퍼뜨리기 위해 필요한 초기 수용자의 최소 수를 하나의 정수로 출력한다.