AT_arc233_c.Equal Degree Deletion
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a tree G with N vertices and N−1 edges.
The vertices are numbered 1 to N, and the edges are numbered 1 to N−1. Edge i connects vertices ui and vi.
A tree H is called special if it is possible to delete all edges of H by performing the following operation zero or more times.
- Choose an edge connecting two vertices whose current degrees are equal, and delete it.
Find the number of special subtrees of G, modulo 998244353.
Solve T test cases for each input.
What is a subtree? A subtree of a tree G is a connected subgraph of G.
给你一棵包含 N 个顶点和 N−1 条边的树 G。
顶点编号为 1 到 N,边编号为 1 到 N−1。第 i 条边连接顶点 ui 和 vi。
若一棵树 H 可通过执行以下操作零次或多次将其中所有边全部删除,则称其为特殊树:
- 选择一条连接两个当前度数相等的顶点的边,并将其删除。
求 G 的特殊子树的数目,结果对 998244353 取模。
对每组输入求解 T 个测试用例。
什么是子树?树 G 的子树是 G 的一个连通子图。
输入格式
The input is given from Standard Input in the following format:
T
case1
case2
⋮
caseT
Each test case caset is given in the following format:
N
u1 v1
u2 v2
⋮
uN−1 vN−1
输入从标准输入中按以下格式给出:
T
case1
case2
⋮
caseT
每个测试用例 caset 按以下格式给出:
N
u1 v1
u2 v2
⋮
uN−1 vN−1
输出格式
Print T lines in total. The t-th line should contain the answer for the t-th test case.
共输出 T 行。第 t 行应包含第 t 个测试用例的答案。
输入输出样例
输入#1
3 6 1 3 2 3 3 4 4 5 4 6 10 2 6 4 5 3 9 6 8 3 5 6 10 3 7 1 10 2 5 2 1 2
输出#1
15 35 3
说明/提示
Sample 1 Explanation:
In the first test case, the 6 subtrees consisting of one vertex and the 5 subtrees consisting of two vertices and one edge are special. Also, the subtree of G consisting of vertices 1,3,4,6 and edges 1,3,5 is special, since the operation can be performed to delete edges 3,5,1 in this order.
Constraints
- 1≤T≤105
- 2≤N≤3×105
- The sum of N over all test cases is at most 3×105.
- 1≤ui<vi≤N
- The given graph G is a tree.
- All input values are integers.
样例 1 解释:
在第一个测试用例中,由单个顶点构成的 6 棵子树,以及由两个顶点和一条边构成的 5 棵子树均为特殊子树。此外,图 G 中由顶点 1,3,4,6 和边 1,3,5 构成的子树也是特殊的,因为可以执行操作,按顺序删除边 3,5,1。
约束条件
- 1≤T≤105
- 2≤N≤3×105
- 所有测试用例的 N 之和不超过 3×105。
- 1≤ui<vi≤N
- 给定图 G 是一棵树。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?