#P18536. Idola-Tree

Idola-Tree

Idola-Tree

偶像组合 Oshikoshi 想请你为新专辑封面设计一件数学艺术品。封面是一棵树:有 nn 位偶像,以及 n−1n-1 条曲线,每条曲线双向连接一对不同的偶像。

简单路径是由至少两位互不相同的偶像组成的序列,相邻偶像之间都有一条曲线。树中任意两个不同顶点之间恰有一条简单路径。从 uu 到 vv 与从 vv 到 uu 算作同一条路径,因此共有 n(n−1)/2n(n-1)/2 条不同的简单路径。

Oshikoshi 给出如下定义:

  • 每条曲线的长度都是正整数。
  • 整棵树的“墨水费用”等于全部 n−1n-1 条曲线的长度之和。
  • 一条简单路径的长度等于这条路径上所有曲线长度之和。
  • 路径的长度平方是先把路径上各条曲线的长度相加,再取平方。例如两条曲线长度分别为 3,43,4,应计算 (3+4)2(3+4)^2,而不是 32+423^2+4^2。
  • 树的“戏剧性”是全部 n(n−1)/2n(n-1)/2 条不同简单路径的长度平方之和。

树的形状已经确定,即哪些偶像之间由曲线直接连接已确定;每条曲线的长度仍待决定。

给定整数 cc,考虑所有使墨水费用恰好等于 cc 的正整数边长分配。令其中最小的戏剧性为 m(c)m(c)。

现在给你整数 CC,请计算

∑c=n−1Cm(c)3(mod998244353).\sum_{c=n-1}^{C}m(c)^3\pmod{998244353}.

上下界均包含在求和范围内,每一个 cc 可以独立选择自己的最优边长分配。

输入格式

第一行一个整数 tt,表示测试用例数。随后依次给出 tt 个测试用例。

每个测试用例第一行两个整数 n,Cn,C。接下来 n−1n-1 行,每行两个 11 到 nn 之间的整数,表示一条曲线直接连接的两位偶像。顶点编号为 11 到 nn。给出的无向图是一棵树。

  • 1≤t≤41\le t\le4;
  • 2≤n≤3⋅1052\le n\le3\cdot10^5;
  • n−1≤C≤5⋅107n-1\le C\le5\cdot10^7。

原题没有额外给出同一输入文件内 nn 或 CC 的总和限制。

输出格式

每个测试用例输出一行,一个整数,表示该测试用例的答案。

原样例

2
4 3
1 4
1 3
2 1
4 4
1 4
1 3
2 1
3375
25327

样例说明

两例使用同一棵树。

  • c=3c=3 时,三条边只能全部取 11,于是 m(3)=12+12+12+22+22+22=15m(3)=1^2+1^2+1^2+2^2+2^2+2^2=15。
  • c=4c=4 时,一种最优分配是把连接偶像 11 与 33 的边长取为 22,其余两条边长为 11。这时 m(4)=12+22+12+32+22+32=28m(4)=1^2+2^2+1^2+3^2+2^2+3^2=28。

所以第一例是 153 mod 998244353=337515^3\bmod998244353=3375,第二例是 (153+283) mod 998244353=25327(15^3+28^3)\bmod998244353=25327。