背景
『想钓到美好的未来。为此得先垂下钓线才行。虽然不是受到那个爱钓鱼的未来人感化,但我试着朝安达抛竿。』
『浸泡在名为命运的河川里久了,就连羁绊也会被水泡软,然后化为碎屑。』
题目描述
给定整数常数 A,B,C,记二次函数 g(x)=Ax2+Bx+C。
给定 m 张无向图 G1∼m,其中第 i 张无向图有 ki 条边,且每张都包含点 1∼n。
定义 A(i,x,y) 为第 i 张图中 x,y 两点的连通性(联通则为 1,否则为 0)。
对于两个点 x,y,定义其联通程度 f(x,y)=i=1∑m[A(i,x,y)=1]。其中 1≤x,y≤n。
对于两个点 x,y,再定义其联通价值 v(x,y)=g(f(x,y))。
现给定一棵由点 1∼n 组成,且以 1 为根的树。求:
$$\prod\limits_{u=1}^{n}(\sum\limits_{1\le x,y \le n}^{}v(x,y)\times [\text{LCA}(x,y)=u])$$
其中 LCA(x,y) 为 x 与 y 的最近公共祖先编号。结果对 998244353 取模。
输入格式
第一行五个整数 n,m,A,B,C。
接下来 m 组,每组第一行一个整数 ki,表示 Gi 的边数。然后 ki 行,每行两个整数 u,v,表示一条边。
接下来 n−1 行,每行两个整数 u,v,表示树上一条边。
输出格式
一行一个整数,表示答案。请注意,负数取模的结果取其非负值。
5 10 4 1 0
1
1 5
5
1 3
1 5
2 4
2 5
4 5
7
1 3
1 4
1 5
2 3
2 4
2 5
3 5
3
1 2
1 4
4 5
2
2 5
3 5
1
1 4
6
1 4
2 3
2 4
2 5
3 4
4 5
2
2 3
3 4
0
1
1 2
2 1
3 2
4 2
5 2
952653543
提示
你是没听到我喊『小樽』吗——!
樽见呢。
保证:
- ∣A∣,∣B∣,∣C∣≤109。
- 1≤n,m≤105。
- 1≤n×m≤105。
- ∑ki≤2×105。
不保证不存在重边、自环。
【样例解释】
下面给出样例中所有 f(x,y) 的值,其中行从上到下表示 x=1…5,列从左到右表示 y=1…5。
| 10 |
5 |
3 |
5 |
| 5 |
10 |
5 |
| 3 |
5 |
10 |
4 |
4 |
| 5 |
4 |
10 |
| 4 |
10 |