{"problem":{"name":"「DROI」Round 1 距离","description":{"content":"定义一棵树 $G$ 上两点 $u,v$ 之间的距离 $\\operatorname{dis}(u,v)$ 为两点之间点的数量。 若对于树上两点 $u,v$，满足 $\\forall x \\in G,\\operatorname{dis}(u,x) \\leq \\operatorname{dis}(u,v)$ **且** $\\operatorname{dis}(v,x) \\leq \\operatornam","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8981"},"statements":[{"statement_type":"Markdown","content":"定义一棵树 $G$ 上两点 $u,v$ 之间的距离 $\\operatorname{dis}(u,v)$ 为两点之间点的数量。\n\n若对于树上两点 $u,v$，满足 $\\forall x \\in G,\\operatorname{dis}(u,x) \\leq \\operatorname{dis}(u,v)$ **且** $\\operatorname{dis}(v,x) \\leq \\operatorname{dis}(u,v)$，那么我们称无序点对 $(u,v)$ 为**极远点对**。\n\n同时，树 $G$ 上一点 $x$ 的权值 $v_x$ 定义为：满足两点间最短路径经过 $x$ 的极远点对的数量。\n\n现给定树 $G$，求 $\\sum\\limits_{x \\in G}{v_x^k}$ 对 $998244353$ 取模的值，其中 $k$ 是给定的常数，且 $k \\in [1,2]$。\n\n## Input\n\n第一行两个数 $n,k$，分别表示树 $G$ 的点数以及给定的常数。\n\n接下来 $n-1$ 行每行两个整数 $u,v$，表示点 $u$ 和点 $v$ 之间有一条边。\n\n## Output\n\n输出一行一个整数，表示答案。\n\n[samples]\n\n## Background\n\n没有什么距离是无法跨越的。\n\n## Note\n\n#### 样例解释 #1\n\n$(1,2)$ 为极远点对，所以 $1$ 号和 $2$ 号点点权均为 $1$，$1^1 + 1^1 =2$。\n\n------------\n\n#### 样例解释 #2\n\n极远点对有 $(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$，故答案为 $4 \\times 3^2 + 6^2 = 72$。\n\n------------\n\n#### 数据范围\n\n| 测试点编号 | $1$ | $2$ | $3$ | $4 \\sim 5$ | $6$ | $7$ | $8 \\sim 9$ | $10$ |\n| :----: | :----: | :----: | :----: | :----: | :----: | :----: | :----: | :----: |\n| $n$ | $300$ | $300$ | $2000$ | $2000$ | $10^5$ | $5 \\times 10^6$ | $10^5$ |  $5 \\times 10^6$|\n| $k$ | $1$ | $2$ | $1$ | $2$ | $1$ | $1$ | $2$ | $2$ |\n\n对于 $100\\%$ 的数据，满足 $n \\leq 5 \\times 10^6$，$1 \\leq  k \\leq 2$。\n\n**本题输入量较大，请用较快的输入方法。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8981","tags":["树形数据结构","洛谷原创","O2优化","树形 DP","树的直径"],"sample_group":[["2 1\n1 2\n","2"],["5 2\n1 2\n1 3\n4 1\n5 1\n","72"]],"created_at":"2026-03-03 11:09:25"}}