루트가 많은 트리?

NYPC 2021 · 예선

우리가 보통 알고 있는 트리는 간선에 방향이 없지만, 다음과 같이 방향이 있는 간선들로 이루어진 트리를 정의할 수 있다.

11부터 NN까지 번호가 매겨져 있는 NN 개의 정점이 있는 방향이 없는 간선들로 이루어진 트리가 주어진다. 이 트리의 모든 간선에 대해서, 방향을 지정해 주려고 한다. 어떤 간선은 방향이 지정되어 있고, 어떤 간선은 아직 방향이 지정되지 않은 상태이다.

방향이 지정되지 않은 간선에 어떤 방향을 주는가에 따라, 이 그래프는 트리가 될 수도 있고 아닐 수도 있다. 만약 트리가 된다면, 이 트리에는 위에서 정의한 루트 정점이 하나 존재한다.

입력으로 주어진 트리에 대해서 간선들에 방향을 정했을 때, 트리의 루트가 될 수 있는 정점의 개수를 구하라.

입력 형식

첫 줄에 트리의 정점 개수를 나타내는 정수 NN이 주어진다. (1N3000001 \le N \le 300\,000)

그 다음 줄부터 N1N-1 개의 줄에 걸쳐, 각 줄마다 간선 하나의 정보를 나타내는 세 정수가 공백으로 구분되어 주어진다. 만약, 정점 aa와 정점 bb를 잇는 간선에 방향이 정해지지 않았다면, 이는 a b 0으로 표현된다. 만약 정점 aa에서 시작해서 정점 bb로 가는 방향이 정해진 간선이라면, 이는 a b 1로 표현된다.

방향 정보를 무시한다면, 주어진 그래프는 트리임에 유의하라.

출력 형식

첫 줄에 방향이 정해지지 않은 간선의 방향을 정했을 때 그 결과가 루트가 있는 트리가 되고, 이때 루트가 될 수 있는 정점들의 개수를 출력한다.

예제

입력

8 5 2 0 8 1 0 5 7 0 4 1 0 5 1 0 3 1 1 5 6 1

출력

1

예제 설명

<그림 1> 입력 예제
<그림 1> 입력 예제

이 그림을 보면, 정점 33은 정점 11을 향해 나가는 간선밖에 없기 때문에 다른 정점에서 이 정점으로 들어올 수 없다. 따라서 다른 정점은 루트가 될 수 없으며, 정점 33이 루트가 될 수 있는지만 확인해보자. 오른쪽 그림과 같이 다른 간선들에 방향을 정하면 정점 33이 루트가 될 수 있음을 알 수 있다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 13

N20N \le 20

종류 2: 24

N3000N \le 3\,000

종류 3: 63

추가적인 제한 조건이 없음.

해설