#PQJ922x4012. QOJ 922_4012
QOJ 922_4012
ZJOI 2022 第二试 深搜(dfs) 深搜(dfs) 【题目描述】 九条可怜是一个喜欢算法的女孩子,在众多算法中她尤其喜欢深度优先搜索(DFS)。 有一天,可怜得到了一棵有根树,树根为root ,树上每个节点x 有一个权值ax。 在一棵树上从x 出发,寻找y 节点,如果使用深度优先搜索,则可描述为以下演算过程:
- 将递归栈设置为空。
- 首先将节点x 放入递归栈中。
- 从递归栈中取出栈顶节点,如果该节点为y,则结束演算过程;否则,如果存在未访问的直接 子节点,则以均等概率随机选择一个子节点加入递归栈中。
- 重复步骤3,直到不存在未访问的直接子节点。
- 将上一级节点加入递归栈中,重复步骤3。
- 重复步骤5,直至当前一级节点为x,演算过程结束。 我们定义f(x, y) 合法当且仅当y 在x 的子树中。它的值为从x 出发,对x 的子树进行深度优 先搜索寻找y 期间访问过的所有节点(包括x 和y)权值最小值的期望。 九条可怜想知道对于所有合法的点对(x, y) ,P f(x, y) 的值。你只需要输出答案对998 244 353 取模的结果。具体地,如果答案的最简分数表示为a b ,输出a × b−1 mod 998 244 353。 【输入格式】 从文件dfs.in 中读入数据。 输入包含多组数据,第一行输入数据组数T 。 对于接下来的每组数据,第一行两个整数n, root ,分别表示树的大小,树根的编号。 接下来一行n 个整数a1, a2, ..., an ,表示树上每个节点的权值。 接下来n −1 行,每行包含两个整数u, v ,表示u 和v 之间有一条树边。 【输出格式】 输出到文件dfs.out 中。 对于每组数据,输出一行,包含一个整数,代表对于所有合法点对(x, y) ,P f(x, y) 对998 244 353 取模的结果。 【样例输入】 见下发文件中的dfs ex1.in和dfs ex2.in。 【样例输出】 见下发文件中的dfs ex1.ans和dfs ex2.ans。 第8 页 共9 页
ZJOI 2022 第二试 深搜(dfs) 【数据范围与提示】 对于所有测试点,满足1 ≤T ≤100,P n ≤800 000,1 ≤n ≤400 000,1 ≤root, u, v ≤n, 1 ≤ai ≤109。 每个测试点的具体限制见下表: 测试点编号 P n ≤ n ≤ 特殊限制 1 50 10 无 2 ∼4 40 000 5 000 无 5 ∼10 400 000 100 000 无 11 800 000 400 000 树的生成方式随机 12 800 000 400 000 树是一条链 13 800 000 400 000 根的度数为n −1 14 ∼20 800 000 400 000 无 对于测试点11,树的生成方式为:以1 为根,对于节点i ∈[2, n],从[1, i −1] 中等概率随机选 择一个点作为父亲。之后将编号随机重排。 第9 页 共9 页