Mock CCC '18 Contest 2 S4 - A Tree Problem

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.6s
Java 1.0s
Memory limit: 1G

Problem type

You are given an undirected tree of N vertices. Every edge in the tree has a color. A path is good if every adjacent pair of edges in the path have different colors. A vertex is good if every simple path starting at that vertex and ending somewhere else in the tree is good.

Compute all good nodes.

Constraints

1 \le N \le 50\,000

1 \le a_i, b_i, c_i \le 50\,000

a_i \neq b_i for all i

In tests worth 5 marks, N \le 10.

Input Specification

The first line contains a single integer N.

Each of the next N-1 lines contains three space-separated integers, a_i, b_i, and c_i, denoting an edge of color c_i connecting vertices a_i and b_i.

Output Specification

On the first line, print k, the number of good vertices.

For each of the next k lines, print the ID of a good vertex. The k lines must be printed in sorted order.

Sample Input 1

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

Sample Output 1

4
3
4
5
6

Sample Input 2

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

Sample Output 2

0

Sample Input 3

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

Sample Output 3

5
1
2
3
6
7

Sample Input 4

10
9 2 1
9 3 1
9 4 2
9 5 2
9 1 3
9 6 4
1 8 5
1 10 5
6 7 9

Sample Output 4

4
1
6
7
9

Comments

There are no comments at the moment.