ZOJ Problem Set - 4134
Recall the definition of a trie:
We say a trie is valid, if the string each vertex represents is distinct.
Given an unrooted tree with $n$ vertices and $(n-1)$ edges, where each edge is marked with a character, how many different vertices can be selected as the root of the tree so that the tree becomes a valid trie?
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the size of the tree.
For the following $(n-1)$ lines, the $i$-th line contains two integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$) and a character $c_i$ separated by a space, indicating that there is an edge marked with a character $c_i$ connecting vertex $u_i$ and $v_i$. It's guaranteed that $c_i$ will only be lower-case English letters.
It's guaranteed that the given graph is a tree, and the sum of $n$ of all test cases will not exceed $10^6$.
For each test case output one line containing one integer, indicating the number of different vertices that can be selected as the root of the tree to make it a valid trie.
2 6 3 1 a 3 2 a 3 4 b 4 5 c 4 6 d 6 3 1 a 3 2 a 3 4 b 5 4 c 6 4 c
Author: CHEN, Jingbang
Source: The 2019 ICPC China Shaanxi Provincial Programming Contest