站外题求助
  • 板块题目总版
  • 楼主SpeedStar
  • 当前回复12
  • 已保存回复12
  • 发布时间2023/2/22 21:01
  • 上次更新2023/10/24 00:04:47
查看原帖
站外题求助
28397
SpeedStar楼主2023/2/22 21:01

给定一颗 NN 个点的无向树,顶点编号分别为 1,2,,N1, 2, \cdots, N,第 ii 条边连接点 AiA_i 和点 BiB_i 。现在考虑从这颗树中砍掉若干条边,从而得到图 GG

假设图 GGkk 个连通分量,且这些连通分量的大小分别为 v1,v2,,vkv_1, v_2, \cdots, v_k,那么 GG 的分数就是 i=1kvi\prod\limits_{i=1}^k v_i

GG2N12^{N-1} 种,要求统计所有 GG 的分数总和,并对其结果模 998244353998244353

数据范围:

  • 2N2×1052 \leqslant N \leqslant 2 \times 10^5
  • 1A<BN1 \leqslant A < B \leqslant N
2023/2/22 21:01
加载中...