A6738 | $「SNOI2024」公交线路$

时间限制1500ms

内存限制1024MB

通过 / 提交0/0

题目描述

给定一棵 $n$ 个点的无根树。我们希望在一些点对之间修建公交线路，满足任意两个点之间只需要至多两条公交线路就能到达。 形式化地说，考虑树上的所有 $\dfrac{n(n-1)}{2}$ 条两个端点不同的简单路径。对于这些路径的一个子集 $S$，称它是好的当且仅当： - 考虑一张新的图 $G$，对于一对点 $u, v$，当且仅当存在 $S$ 中的一条路径 $P$，满足 $u$ 和 $v$ 都在 $P$ 上，我们会在 $u,v$ 之间连上边权为 $1$ 的无向边。 - 要求 $G$ 中任意两点之间的距离都不超过 $2$。 你需要求出有多少个子集 $S$ 是好的。由于答案可能很大，输出对 $998244353$ 取模的结果。

第一行，一个正整数 $n$ 表示节点个数。 接下来 $n - 1$ 行，每行两个正整数 $u, v$，表示一条树边 $(u, v)$。

输出一个整数，表示答案对 $998244353$ 取模的结果。

输入 #1

3
1 2
2 3

输出 #1

输入 #2

输出 #2

C++ 编辑器

输入

输出