[SNOI2024] 公交线路

Luogu
IDLGP10064
Time1500ms
Memory1024MB
DifficultyP7
各省省选2024O2优化陕西
给定一棵 $n$ 个点的无根树。我们希望在一些点对之间修建公交线路,满足任意两个点之间只需要至多两条公交线路就能到达。 形式化地说,考虑树上的所有 $\frac{n (n - 1)}{2}$ 条两个端点不同的简单路径。对于这些路径的一个子集 $S$,称它是好的当且仅当: - 考虑一张新的图 $G$,对于一对点 $u, v$,当且仅当存在 $S$ 中的一条路径 $P$,满足 $u$ 和 $v$ 都在 $P$ 上,我们会在 $u, v$ 之间连上边权为 $1$ 的无向边。 - 要求 $G$ 中任意两点之间的距离都不超过 $2$。 你需要求出有多少个子集 $S$ 是好的。由于答案可能很大,输出对 $998244353$ 取模的结果。 ## Input 第一行,一个正整数 $n$ 表示节点个数。 接下来 $n - 1$ 行,每行两个正整数 $u, v$,表示一条树边 $(u, v)$。 ## Output 输出一个整数,表示答案对 $998244353$ 取模的结果。 [samples] ## Note **【样例 \#1 解释】** 对于对于第一个样例,所有可行的方案为 $\{(1, 3)\}, \{(1, 3), (1, 2)\}, \{(1, 3), (2, 3)\}, \{(1, 3), (1, 2), (2, 3)\}, \{(1, 2), (2, 3)\}$。 --- **【样例 \#3】** 见附件中 `bus/bus3.in` 与 `bus/bus3.ans`。 这个样例满足测试点 $11 \sim 14$ 的条件限制。 --- **【样例 \#4】** 见附件中 `bus/bus4.in` 与 `bus/bus4.ans`。 这个样例满足测试点 $19 \sim 20$ 的条件限制。 --- **【数据范围】** 对于所有的数据,保证 $1 \le n \le 3000$。 具体如下: | 测试点编号 | $n \le$ | 特殊性质 | |:-:|:-:|:-:| | $1 \sim 3$ | $6$ | 无 | | $4 \sim 7$ | $10$ | 无 | | $8 \sim 10$ | $3000$ | A | | $11 \sim 14$ | $100$ | 无 | | $15 \sim 18$ | $500$ | 无 | | $19 \sim 20$ | $3000$ | 无 | 特殊性质 A:保证树是一条链。
Samples
Input #1
3
1 2
2 3
Output #1
5
Input #2
6
1 2
2 3
2 4
3 5
3 6
Output #2
27296
API Response (JSON)
{
  "problem": {
    "name": "[SNOI2024] 公交线路",
    "description": {
      "content": "给定一棵 $n$ 个点的无根树。我们希望在一些点对之间修建公交线路,满足任意两个点之间只需要至多两条公交线路就能到达。 形式化地说,考虑树上的所有 $\\frac{n (n - 1)}{2}$ 条两个端点不同的简单路径。对于这些路径的一个子集 $S$,称它是好的当且仅当: - 考虑一张新的图 $G$,对于一对点 $u, v$,当且仅当存在 $S$ 中的一条路径 $P$,满足 $u$ 和 $v$ 都",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10064"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一棵 $n$ 个点的无根树。我们希望在一些点对之间修建公交线路,满足任意两个点之间只需要至多两条公交线路就能到达。\n\n形式化地说,考虑树上的所有 $\\frac{n (n - 1)}{2}$ 条两个端点不同的简单路径。对于这些路径的一个子集 $S$,称它是好的当且仅当:\n- 考虑一张新的图 $G$,对于一对点 $u, v$,当且仅当存在 $S$ 中的一条路径 $P$,满足 $u$ 和 $v$ 都...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments