| 2026-2027 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals) |
|---|
| Закончено |
Beatrice has a tree $$$T$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, each of degree at most three. She considers all possible ways to assign the keys $$$1, 2, \ldots, n$$$ to the vertices, with one key per vertex and each key used exactly once. Let $$$k_i$$$ be the key assigned to vertex $$$i$$$.
After assigning the keys, Beatrice can choose a vertex as the root of $$$T$$$ and designate the children of each vertex as left or right. The resulting tree is a binary search tree if the following conditions hold:
For a fixed assignment of keys, a vertex $$$r$$$ is a valid root if $$$T$$$ can be made into a binary search tree rooted at $$$r$$$ by designating each child as left or right. The search quality of the assignment is the number of valid roots.
For the given tree $$$T$$$, find the sum of the search qualities of all possible assignments, modulo $$$998\,244\,353$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains an integer $$$n$$$, denoting the number of vertices ($$$2 \le n \le 2 \cdot 10^5$$$).
Each of the following $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$, denoting the endpoints of an edge ($$$1 \le u, v \le n$$$; $$$u \ne v$$$). The edges form a tree in which every vertex has degree at most three.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print the sum of the search qualities of all assignments, modulo $$$998\,244\,353$$$.
331 22 343 22 41 251 33 55 45 2
101228
For the first test case, the valid roots for each assignment are:
| Keys $$$(k_1,k_2,k_3)$$$ | $$$(1,2,3)$$$ | $$$(1,3,2)$$$ | $$$(2,1,3)$$$ | $$$(2,3,1)$$$ | $$$(3,1,2)$$$ | $$$(3,2,1)$$$ |
| Valid roots (vertex numbers) | $$$\{1,2,3\}$$$ | $$$\{1\}$$$ | $$$\{3\}$$$ | $$$\{3\}$$$ | $$$\{1\}$$$ | $$$\{1,2,3\}$$$ |
| Название |
|---|


