#PQJ2294x13460. QOJ 2294_13460

    ID: 2793 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训数学

QOJ 2294_13460

标题: Communication Network - Problem - QOJ.ac

Statistics

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 量较大,请使用较快速的读入方法。