
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 $(n1)$ 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? InputThere 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 $(n1)$ 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 lowercase 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$. OutputFor 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. Sample Input2 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 Sample Output2 0 Author: CHEN, Jingbang Source: The 2019 ICPC China Shaanxi Provincial Programming Contest 