#P17752. 黎明之曦
黎明之曦
题目背景
feluamn 历经千辛万苦,终于到达了光明山脉的外围。黑色的夜空由于光明之巅的照耀,泛出一丝湖蓝色。感受到山脉深处浓郁的光明气息,feluamn 看到了希望。
或许是因为过于激动,她不幸落入了蛮人族的掌心。由于feluamn 是破开黑暗的唯一希望,蛮人族并没有蹂躏可怜的feluamn 。但是feluamn 需要展现出足够的能力,蛮人族族长才肯让她前去光明之巅一试。
题目描述
蛮人族正在筹划洗劫暗夜贵族。光明山脉地势复杂,这给他们带来了便利。
光明山脉的通路可以看做是一个有n 个点,n −1 条双向边组成的联通图。蛮人族计划洗劫暗夜贵族的k 条交通路线,第i 条是从 到 的简单路径。
蛮人族准备了一个土系禁咒,分布在了两个节点u 和v 。当暗夜贵族的商队经过u 后又经过v ,或者经过v 后又经过u ,就会触发禁咒。
由于禁咒威力强大,为了防止禁咒的两部分靠的太近而产生共鸣(这样更容易被发现)或者造成不必要的破坏,蛮人族将它们尽量放在相距较远的地方(当然,蛮人族并不会因此而放过任意一条计划洗劫的商路),且这两部分不可能在同一个节点。
由于手下的疏忽,现在蛮人族族长只知道这两个节点计划放在哪里,但不知道计划洗劫的商路的情况。蛮人族族长想让聪明可爱的feluamn 告诉他可能的方案数。注意商路从1 到k 标了号,并且(u, v) 和(v, u) 视为同一条商路。两个方案不同当且仅当存在至少一个i ,使得两个方案的第i 条商路不同。
虽然蛮人族族长的智商并不高,但是路途的疲惫加上问题数量众多,feluamn有些疲于应对。这正是英雄救美的好时机!你能帮帮feluamn 吗?
输入格式
从标准输入读入。
第一行一个正整数T 表示数据组数。
对于每组数据,第一行两个正整数n 和q ,表示点数和问题数量。
接下来n −1 行,每行两个整数x, y ,表示x 与y 之间有一条双向边。
接下来q 行,每行三个正整数k ,x 和y ,表示一组询问,x ,y 为禁咒两个部分的位置。
输出格式
输出到标准输出。
每组数据输出q 行,代表询问的答案。但由于蛮人族族长的智商不足以处理太大的数据,请将答案对998244353 取模。
注意你并不需要在两组数据之间输出空行。
样例
样例1 输入
1
5 1
1 2
1 3
2 4
2 5
2 1 2
样例1 输出
21
样例2 输入
1
3 1
1 2
2 3
4 1 2
样例2 输出
15
数据范围与约定
对于所有数据T ⩽5 ,1 ⩽n, q ⩽100000 ,1 ⩽x, y ⩽n ,1 ⩽k ⩽100 。
• subtask1(20%):n, q ⩽500 ,k ⩽2 ;
• subtask2(20%):k ⩽2 ;
• subtask3(15%):k ⩽10 。
• subtask4(15%):对于每条边,有x + 1 = y ;
• subtask5(10%):每个点的度数不超过4 。
• subtask6(20%):无特殊限制。