[ECUSTPC 2025] 荷塘月色 - 题目

内存限制：1024 MiB 时间限制：3000 ms 标准输入输出

题目类型：VJudge（洛谷）评测方式：VJudge

上传者：匿名

提交提交记录统计讨论题解

Maddy 碰到了朵朵绽放的荷花，但荷花之中又透露了一丝诡异……
在这个荷花池中，有一棵具有个结点的树，这是一个由条边连成的无向无环连通图。
每个结点 () 都带有的权值，而一棵树的 -点对定义如下：

Maddy 现在在树上随机选取两个不同的点，如果存在满足是 -点对，则她会得到个灯笼。
请帮助 Maddy 求出其期望获得的灯笼数对取模的值，具体的输出要求请参照提示。

第一行输入一个整数 ()，表示数据组数。
每组测试数据输入的第一行输入一个整数 ()，表示图的顶点数量。
随后行每行输入两个整数和 ()，表示树上存在一条到的边。
随后一行输入个整数 () 分别表示树上点的权值。
保证所有测试数据输入中的，且每组数据输入的图构成一棵树。

对于每组测试数据，输出一行一个整数表示 Maddy 期望获得的灯笼数对取模的值。

1
6
1 2
1 3
2 4
2 5
3 6
6 2 3 4 2 1

332748119

给定的树共有 6 个点，边为

权值分别为

我们枚举所有对点，检查路径上的权值集合的与是否相等。
例如：

最终统计结果如下：
：5 对，
：6 对，
：1 对，
：0 对。

可以求得对应的期望灯笼数为

对应取模得到答案。

可以证明本题的答案会是一个有理数，记这个答案是其中互质，你需要输出的数字须满足在之内且

可以证明这样的在题目意义下一定存在。

编辑器加载中 …

或者，上传代码文件

Powered by SYZOJ. Modified by Zemu (UnratedCheater).

当前版本：V1.7.2-premium

#216262. [ECUSTPC 2025] 荷塘月色