{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eRecall the definition of a trie:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eA trie of size $n$ is a rooted tree with $n$ vertices and $(n-1)$ edges, where each edge is marked with a character;\u003c/li\u003e\n\u003cli\u003eEach vertex in a trie represents a string. Let $s(x)$ be the string vertex $x$ represents;\u003c/li\u003e\n\u003cli\u003eThe root of the trie represents an empty string. Let vertex $u$ be the parent of vertex $v$, and let $c$ be the character marked on the edge connecting vertex $u$ and $v$, we have $s(v)$ \u003d $s(u) + c$. Here $+$ indicates string concatenation, not the normal addition operation.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eWe say a trie is valid, if the string each vertex represents is distinct.\u003c/p\u003e\n\u003cp\u003eGiven 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?\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^5$), indicating the size of the tree.\u003c/p\u003e\n\u003cp\u003eFor 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\u0027s guaranteed that $c_i$ will only be lower-case English letters.\u003c/p\u003e\n\u003cp\u003eIt\u0027s guaranteed that the given graph is a tree, and the sum of $n$ of all test cases will not exceed $10^6$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor 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.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n6\n3 1 a\n3 2 a\n3 4 b\n4 5 c\n4 6 d\n6\n3 1 a\n3 2 a\n3 4 b\n5 4 c\n6 4 c\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}