English · Original
Chinese · Translation
Formal · Original
You are given a tree of $n$ vertices. You are to select $k$ (not necessarily distinct) simple paths in such a way that it is possible to split all edges of the tree into three sets: edges not contained in any path, edges that are a part of exactly one of these paths, and edges that are parts of all selected paths, and the latter set should be non-empty.
Compute the number of ways to select $k$ paths modulo $998244353$.
The paths are enumerated, in other words, two ways are considered distinct if there are such $i$ ($1 \leq i \leq k$) and an edge that the $i$\-th path contains the edge in one way and does not contain it in the other.
## Input
The first line contains two integers $n$ and $k$ ($1 \leq n, k \leq 10^{5}$) — the number of vertices in the tree and the desired number of paths.
The next $n - 1$ lines describe edges of the tree. Each line contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$) — the endpoints of an edge. It is guaranteed that the given edges form a tree.
## Output
Print the number of ways to select $k$ enumerated not necessarily distinct simple paths in such a way that for each edge either it is not contained in any path, or it is contained in exactly one path, or it is contained in all $k$ paths, and the intersection of all paths is non-empty.
As the answer can be large, print it modulo $998244353$.
[samples]
## Note
In the first example the following ways are valid：
* $((1,2), (1,2))$,
* $((1,2), (1,3))$,
* $((1,3), (1,2))$,
* $((1,3), (1,3))$,
* $((1,3), (2,3))$,
* $((2,3), (1,3))$,
* $((2,3), (2,3))$.
In the second example $k=1$, so all $n \cdot (n - 1) / 2 = 5 \cdot 4 / 2 = 10$ paths are valid.
In the third example, the answer is $\geq 998244353$, so it was taken modulo $998244353$, don't forget it!
你被给定一棵包含 $n$ 个顶点的树。你需要选择 $k$ 个（不一定互不相同的）简单路径，使得所有边可以被划分为三个集合：不在任何路径中的边、恰好属于其中一个路径的边、以及属于所有选定路径的边，且后一个集合不能为空。
请计算选择 $k$ 条路径的方案数，对 $998244353$ 取模。
路径是有序的，换句话说，两种方式被视为不同，当且仅当存在某个 $i$（$1 lt.eq i lt.eq k$）和一条边，使得在一种方式中第 $i$ 条路径包含该边，而在另一种方式中不包含。
第一行包含两个整数 $n$ 和 $k$（$1 lt.eq n, k lt.eq 10^5$）——树的顶点数和所需的路径数。
接下来 $n - 1$ 行描述树的边。每行包含两个整数 $a$ 和 $b$（$1 lt.eq a, b lt.eq n$，$a != b$）——边的两个端点。保证给出的边构成一棵树。
请输出选择 $k$ 个有序的、不一定互不相同的简单路径的方案数，满足条件：对于每条边，要么它不属于任何路径，要么它恰好属于一条路径，要么它属于所有 $k$ 条路径，且所有路径的交集非空。由于答案可能很大，请对 $998244353$ 取模。
在第一个例子中，以下方式是有效的：
在第二个例子中，$k = 1$，因此所有 $n dot.op (n -1) \/ 2 = 5 dot.op 4 \/ 2 = 10$ 条路径都是有效的。
在第三个例子中，答案 $gt.eq 998244353$，因此已对其取模 $998244353$，请勿忘记这一点！
## Input
第一行包含两个整数 $n$ 和 $k$（$1 lt.eq n, k lt.eq 10^5$）——树的顶点数和所需的路径数。接下来 $n -1$ 行描述树的边。每行包含两个整数 $a$ 和 $b$（$1 lt.eq a, b lt.eq n$，$a != b$）——边的两个端点。保证给出的边构成一棵树。
## Output
请输出选择 $k$ 个有序的、不一定互不相同的简单路径的方案数，满足条件：对于每条边，要么它不属于任何路径，要么它恰好属于一条路径，要么它属于所有 $k$ 条路径，且所有路径的交集非空。由于答案可能很大，请对 $998244353$ 取模。
[samples]
## Note
在第一个例子中，以下方式是有效的：$((1, 2), (1, 2))$，$((1, 2), (1, 3))$，$((1, 3), (1, 2))$，$((1, 3), (1, 3))$，$((1, 3), (2, 3))$，$((2, 3), (1, 3))$，$((2, 3), (2, 3))$。在第二个例子中，$k = 1$，因此所有 $n dot.op (n -1) \/ 2 = 5 dot.op 4 \/ 2 = 10$ 条路径都是有效的。在第三个例子中，答案 $gt.eq 998244353$，因此已对其取模 $998244353$，请勿忘记这一点！
**Definitions**
Let $ T = (V, E) $ be a tree with $ n $ vertices and $ n-1 $ edges.
Let $ \mathcal{P} $ be the set of all simple paths in $ T $.
Let $ k \in \mathbb{Z}^+ $ be the number of selected (enumerated, not necessarily distinct) paths: $ P_1, P_2, \dots, P_k \in \mathcal{P} $.
For each edge $ e \in E $, define its *coverage* $ c(e) = |\{ i \in \{1, \dots, k\} : e \in P_i \}| $.
Let $ \mathcal{S} $ be the set of all $ k $-tuples $ (P_1, \dots, P_k) $ such that:
- For every $ e \in E $, $ c(e) \in \{0, 1, k\} $,
- $ \bigcap_{i=1}^k P_i \neq \emptyset $ (i.e., there exists at least one edge $ e \in E $ such that $ c(e) = k $).
**Constraints**
1. $ 1 \le n, k \le 10^5 $
2. $ T $ is a tree on $ n $ vertices.
**Objective**
Compute $ |\mathcal{S}| \mod 998244353 $.
API Response (JSON)
{
"problem": {
"name": "H. K Paths",
"description": {
"content": "You are given a tree of $n$ vertices. You are to select $k$ (not necessarily distinct) simple paths in such a way that it is possible to split all edges of the tree into three sets: edges not containe",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF981H"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given a tree of $n$ vertices. You are to select $k$ (not necessarily distinct) simple paths in such a way that it is possible to split all edges of the tree into three sets: edges not containe...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一棵包含 $n$ 个顶点的树。你需要选择 $k$ 个（不一定互不相同的）简单路径，使得所有边可以被划分为三个集合：不在任何路径中的边、恰好属于其中一个路径的边、以及属于所有选定路径的边，且后一个集合不能为空。\n\n请计算选择 $k$ 条路径的方案数，对 $998244353$ 取模。\n\n路径是有序的，换句话说，两种方式被视为不同，当且仅当存在某个 $i$（$1 lt.eq i lt.eq k...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ T = (V, E) $ be a tree with $ n $ vertices and $ n-1 $ edges. \nLet $ \\mathcal{P} $ be the set of all simple paths in $ T $. \nLet $ k \\in \\mathbb{Z}^+ $ be the number of selec...",
"is_translate": false,
"language": "Formal"
}
]
}