#PQJ2294x13460. QOJ 2294_13460
QOJ 2294_13460
标题: Communication Network - Problem - QOJ.ac
The problem was used in the following contests:
小 H 在玩一款游戏。
这是一款对城市进行建设的游戏,游戏里有 n 个城市。
为了使城市之间能够通信,小 H 用 n−1 条边连接了城市。对于一条边 (x,y),它保证了城市 x 和城市 y 能直接通信。通过这些边,任意两个城市能够直接或间接通信。
不难发现,上述做法存在一些问题。对于两座城市,如果它们之间需要经过的中转站越多,那么每次发送信息所需要的时间就越长。这就导致一些城市通信便利,一些城市通信不便利。
然而,增加边的数量会导致小 H 无法管理而出现问题。为了解决这个矛盾,小 H 想出了一个办法,每经过一段固定的时间,就重新随机的构建一次网络。这样一来,任意两个城市通信时间的期望值都是相等的。
然而,重构网络也是需要代价的。假设原网络为 T1,新网络为 T2,假设两个网络有 x 条边是一样的,那么小 H 在调整时就可以忽略这些边。
自然,能忽略的边越多越好,因此小 H 认为这种方案的的价值为 x⋅2x。
现在,小H将进行第一次网络重构,请问,所有方案的价值之和为多少?
当然,这个答案比较大,所有你只需要求其对 998244353 取模的值。
形式化题目
给定树 T1={V,E1},|V|=n,假设点集 V 能构成的生成树集合为 S,你需要求:
(∑T2∈S|E1∩E2|⋅2|E1∩E2|)mod998244353
不难发现,|S|=nn−2。
输入格式
第一行一个整数 n 。
接下来 n−1 行,每行两个整数 xi,yi ,描述 T1 上的一条边。
输出格式
输出一行,表示价值之和对 998244353 取模的结果。
样例数据
样例 1 输入
4
1 2
2 3
3 4
样例 1 输出
94
样例 1 解释
对于含有 3 条边的生成树,只有 1 种。故贡献为 3×23=24。
对于含有 2 条边的生成树,分类讨论。如果没选 (1,2) 或 (3,4),那么各有 2 种。如果没选 (2,3),那么有 3 种。故贡献为 7×2×22=56。
对于含有 1 条边的生成树,如果选了 (1,2) 或 (3,4),那么各有 2 种。如果选了 (2,3),那么有 3 种。故贡献为 7×2=14。
答案为 24+56+14=94。
子任务
本题采用捆绑测试。
对于所有数据,满足 1≤n≤2×106 。
子任务见下表:
子任务编号 n 特殊性质 分值 1 ≤80 无 5 2 ≤300 无 5 3 ≤3000 特殊性质 A 5 4 ≤3000 特殊性质 B 5 5 ≤3000 无 10 6 ≤105 特殊性质 A 10 7 ≤105 特殊性质 B 10 8 ≤2×106 特殊性质 A 10 9 ≤2×106 特殊性质 B 10 10 ≤2×106 无 30
表中的特殊性质如下:
- 特殊性质 A:图是一条链。
- 特殊性质 B:图是一张菊花图。
提示
本题 IO 量较大,请使用较快速的读入方法。