75 lines
1.3 KiB
Python
75 lines
1.3 KiB
Python
from queue import Queue
|
|
|
|
n = int(input())
|
|
|
|
tree = {i: [] for i in range(1, n + 1)}
|
|
|
|
for i in range(n - 1):
|
|
a, b, c = map(int, input().strip().split())
|
|
|
|
tree[a].append((b, c))
|
|
tree[b].append((a, c))
|
|
|
|
keys = list(tree)
|
|
|
|
bad_paths = {}
|
|
|
|
|
|
def recdel(n, root):
|
|
global bad_paths
|
|
|
|
if bad_paths == 'ALL':
|
|
return
|
|
|
|
q = Queue()
|
|
q.put((n, root))
|
|
|
|
while not q.empty():
|
|
n, root = q.get()
|
|
|
|
if n not in tree:
|
|
continue
|
|
|
|
if n in bad_paths and bad_paths[n] == root:
|
|
continue
|
|
|
|
if root in bad_paths and bad_paths[root] == n:
|
|
bad_paths = 'ALL' # needs global
|
|
return
|
|
|
|
bad_paths[n] = root
|
|
|
|
neighbors = tree[n]
|
|
|
|
for e, _ in neighbors:
|
|
if e == root:
|
|
continue
|
|
q.put((e, n))
|
|
|
|
|
|
for f in keys:
|
|
if f not in tree:
|
|
continue
|
|
|
|
edges = tree[f]
|
|
all_colors = set()
|
|
bad_colors = set()
|
|
|
|
for t, c in edges:
|
|
if c in all_colors:
|
|
bad_colors.add(c)
|
|
else:
|
|
all_colors.add(c)
|
|
|
|
for t, c in edges:
|
|
if c in bad_colors:
|
|
recdel(t, f)
|
|
|
|
all_good = set()
|
|
if bad_paths != 'ALL':
|
|
all_good = set(tree) - set(bad_paths)
|
|
|
|
print(len(all_good))
|
|
for i in sorted(all_good):
|
|
print(i)
|