{"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 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.\n\nCompute the number of ways to select $k$ paths modulo $998244353$.\n\nThe 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.\n\n## Input\n\nThe 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.\n\nThe 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.\n\n## Output\n\nPrint 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.\n\nAs the answer can be large, print it modulo $998244353$.\n\n[samples]\n\n## Note\n\nIn the first example the following ways are valid：\n\n*   $((1,2), (1,2))$,\n*   $((1,2), (1,3))$,\n*   $((1,3), (1,2))$,\n*   $((1,3), (1,3))$,\n*   $((1,3), (2,3))$,\n*   $((2,3), (1,3))$,\n*   $((2,3), (2,3))$.\n\nIn the second example $k=1$, so all $n \\cdot (n - 1) / 2 = 5 \\cdot 4 / 2 = 10$ paths are valid.\n\nIn the third example, the answer is $\\geq 998244353$, so it was taken modulo $998244353$, don't forget it!","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$）和一条边，使得在一种方式中第 $i$ 条路径包含该边，而在另一种方式中不包含。\n\n第一行包含两个整数 $n$ 和 $k$（$1 lt.eq n, k lt.eq 10^5$）——树的顶点数和所需的路径数。\n\n接下来 $n - 1$ 行描述树的边。每行包含两个整数 $a$ 和 $b$（$1 lt.eq a, b lt.eq n$，$a != b$）——边的两个端点。保证给出的边构成一棵树。\n\n请输出选择 $k$ 个有序的、不一定互不相同的简单路径的方案数，满足条件：对于每条边，要么它不属于任何路径，要么它恰好属于一条路径，要么它属于所有 $k$ 条路径，且所有路径的交集非空。由于答案可能很大，请对 $998244353$ 取模。\n\n在第一个例子中，以下方式是有效的：\n\n在第二个例子中，$k = 1$，因此所有 $n dot.op (n -1) \\/ 2 = 5 dot.op 4 \\/ 2 = 10$ 条路径都是有效的。\n\n在第三个例子中，答案 $gt.eq 998244353$，因此已对其取模 $998244353$，请勿忘记这一点！\n\n## Input\n\n第一行包含两个整数 $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$）——边的两个端点。保证给出的边构成一棵树。\n\n## Output\n\n请输出选择 $k$ 个有序的、不一定互不相同的简单路径的方案数，满足条件：对于每条边，要么它不属于任何路径，要么它恰好属于一条路径，要么它属于所有 $k$ 条路径，且所有路径的交集非空。由于答案可能很大，请对 $998244353$ 取模。\n\n[samples]\n\n## Note\n\n在第一个例子中，以下方式是有效的：$((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$，请勿忘记这一点！","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 selected (enumerated, not necessarily distinct) paths: $ P_1, P_2, \\dots, P_k \\in \\mathcal{P} $.  \n\nFor each edge $ e \\in E $, define its *coverage* $ c(e) = |\\{ i \\in \\{1, \\dots, k\\} : e \\in P_i \\}| $.  \n\nLet $ \\mathcal{S} $ be the set of all $ k $-tuples $ (P_1, \\dots, P_k) $ such that:  \n- For every $ e \\in E $, $ c(e) \\in \\{0, 1, k\\} $,  \n- $ \\bigcap_{i=1}^k P_i \\neq \\emptyset $ (i.e., there exists at least one edge $ e \\in E $ such that $ c(e) = k $).\n\n**Constraints**  \n1. $ 1 \\le n, k \\le 10^5 $  \n2. $ T $ is a tree on $ n $ vertices.  \n\n**Objective**  \nCompute $ |\\mathcal{S}| \\mod 998244353 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF981H","tags":["combinatorics","data structures","dp","fft","math"],"sample_group":[["3 2\n1 2\n2 3","7"],["5 1\n4 1\n2 3\n4 5\n2 1","10"],["29 29\n1 2\n1 3\n1 4\n1 5\n5 6\n5 7\n5 8\n8 9\n8 10\n8 11\n11 12\n11 13\n11 14\n14 15\n14 16\n14 17\n17 18\n17 19\n17 20\n20 21\n20 22\n20 23\n23 24\n23 25\n23 26\n26 27\n26 28\n26 29","125580756"]],"created_at":"2026-03-03 11:00:39"}}