Énoncé
Notez la définition inhabituelle de sous-arbre et de diamètre dans ce problème. Voici quelques définitions :
- La taille d'un arbre $T$ est le nombre de sommets qu'il contient, c'est-à-dire $|V(T)|$.
- Le degré d'un sommet $i$ dans un arbre $T$ est le nombre d'arêtes connectées à lui, noté $deg_i$.
- Un arbre $T'$ est un sous-arbre de l'arbre $T$ si et seulement si :
- Pour tous les sommets $v \in V(T')$, $v \in V(T)$.
- Pour toutes les arêtes $e \in E(T')$, $e \in E(T)$.
- Soit $S_T$ l'ensemble des sous-arbres de $T$.
- Le diamètre d'un arbre $T$ est la taille du plus grand sous-arbre de $T$ tel que $max(deg_i) \le 2$ dans le sous-arbre.
- Soit $R_k$ l'ensemble des plus grands arbres tels que :
- $max(deg_i) \le 3$.
- Le diamètre de l'arbre est $2k$.
- Pour un arbre $T$, soit $f(T)$ le plus grand $k$ tel que $S_T \cap R_k \neq \emptyset$. S'il n'existe pas un tel $k$, $f(T) = 0$.
On vous donne un arbre $T$ avec $n$ sommets. Comptez la somme de $f(T')$ pour tous les sous-arbres $T'$ de $T$ modulo 998244353. Deux sous-arbres sont différents si et seulement si ils ont un ensemble de sommets ou un ensemble d'arêtes différent.
Entrée
Chaque cas de test contient plusieurs cas de test. La première ligne contient un entier $t$ ($1 \le t \le 5 \times 10^4$), indiquant le nombre de cas de test. La description des cas de test suit. La première ligne contient un entier $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), indiquant le nombre de sommets dans l'arbre $T$. Les $n-1$ lignes suivantes contiennent deux entiers $u, v$ ($1 \le u \neq v \le n$), indiquant une arête de l'arbre $T$.
Sortie
Pour chaque cas de test, imprimez un entier, indiquant la somme de $f(T')$, modulo 998244353.
Exemples
Entrée 1
5 1 2 1 3 2 4 2 5
Sortie 1
12
Entrée 2
8 1 2 1 3 8 7 1 9 8 6 1 4 8 5
Sortie 2
94
Remarque
Pour le premier cas de test, il y a 17 sous-arbres différents. 5 des sous-arbres ne contiennent qu'un seul sommet et donc $f(T') = 0$. Tous les autres sous-arbres satisfont $f(T') = 1$. Ainsi, la réponse est 12.