#P17943. Embedding Trees

Embedding Trees

Embedding Trees

本题的子树和直径定义需要特别注意。

  • 树 TT 的大小为顶点数 ∣V(T)∣|V(T)|。
  • 顶点的度数是与它相连的边数。
  • 一棵树 T′T' 是 TT 的子树,当且仅当 V(T′)⊆V(T)V(T')\subseteq V(T) 且 E(T′)⊆E(T)E(T')\subseteq E(T)。这里的子树可以是任意非空连通子图,并不限于选定根后的某个完整根式子树。
  • 记 STS_T 为 TT 的所有子树组成的集合。
  • 树的直径定义为:所有最大度数不超过 22 的子树中,最大的顶点数。也就是最长简单路径的点数。
  • 对正整数 xx,在所有最大度数不超过 33、直径恰好为 2x2x 的树中,取大小最大的那些树,组成集合 RxR_x。
  • 定义 f(T)f(T) 为满足 ST∩Rk≠∅S_T\cap R_k\ne\varnothing 的最大正整数 kk;若不存在这样的 kk,则 f(T)=0f(T)=0。

给定一棵 nn 个顶点的树 TT,计算

∑T′∈STf(T′)(mod998244353).\sum_{T'\in S_T}f(T')\pmod{998244353}.

两个子树不同,当且仅当顶点集合或边集合不同。

输入格式

第一行是测试用例数 tt,1≤t≤5×1041\le t\le5\times10^4。

每组用例第一行包含 nn。接下来 n−1n-1 行,每行两个整数 u,vu,v,表示树的一条边。

1≤n≤1051\le n\le10^5,1≤u,v≤n1\le u,v\le n,u≠vu\ne v;所有用例的 ∑n≤106\sum n\le10^6。保证输入是一棵树。

输出格式

每组用例输出一行一个整数,表示所求和对 998244353998244353 取模的结果。

样例 1

2
5
1 2
1 3
2 4
2 5
8
1 2
8 7
1 3
8 6
1 4
8 5
1 8
12
94

第一组样例共有17棵子树,其中5棵只有一个顶点、贡献为0,其余12棵的 ff 值均为1。