33OJ
登录 注册

#P17776. 岛村抱月不是罪过

岛村抱月不是罪过

背景

『想钓到美好的未来。为此得先垂下钓线才行。虽然不是受到那个爱钓鱼的未来人感化,但我试着朝安达抛竿。』

『浸泡在名为命运的河川里久了,就连羁绊也会被水泡软,然后化为碎屑。』

题目描述

给定整数常数 A,B,CA,B,C,记二次函数 g(x)=Ax2+Bx+Cg(x) = Ax^2+Bx+C。

给定 mm 张无向图 G1∼mG_{1\sim m},其中第 ii 张无向图有 kik_i 条边,且每张都包含点 1∼n1\sim n。

定义 A(i,x,y)A(i,x,y) 为第 ii 张图中 x,yx,y 两点的连通性(联通则为 11,否则为 00)。

对于两个点 x,yx,y,定义其联通程度 f(x,y)=∑i=1m[A(i,x,y)=1]f(x,y) =\sum\limits_{i=1}^{m}[A(i,x,y)=1]。其中 1≤x,y≤n1 \le x,y \le n。

对于两个点 x,yx,y,再定义其联通价值 v(x,y)=g(f(x,y))v(x,y) = g(f(x,y))。

现给定一棵由点 1∼n1\sim n 组成,且以 11 为根的树。求:

$$\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)\text{LCA}(x,y) 为 xx 与 yy 的最近公共祖先编号。结果对 998244353998244353 取模。

输入格式

第一行五个整数 n,m,A,B,Cn,m,A,B,C。

接下来 mm 组,每组第一行一个整数 kik_i,表示 GiG_i 的边数。然后 kik_i 行,每行两个整数 u,vu,v,表示一条边。

接下来 n−1n-1 行,每行两个整数 u,vu,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|A|,|B|,|C| \le 10^9。
  • 1≤n,m≤1051 \le n, m \le 10^5。
  • 1≤n×m≤1051 \le n \times m \le 10^5。
  • ∑ki≤2×105\sum k_i \le 2\times 10^5。

不保证不存在重边、自环。

【样例解释】

下面给出样例中所有 f(x,y)f(x,y) 的值,其中行从上到下表示 x=1…5x=1\dots 5,列从左到右表示 y=1…5y=1\dots 5。

1010 55 33 55
55 1010 55
33 55 1010 44 44
55 44 1010
44 1010