「DROI」Round 1 距离

Luogu

IDLGP8981

Time1000ms

Memory512MB

DifficultyP5

树形数据结构洛谷原创O2优化树形 DP树的直径

定义一棵树 $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 \operatorname{dis}(u,v)$，那么我们称无序点对 $(u,v)$ 为**极远点对**。同时，树 $G$ 上一点 $x$ 的权值 $v_x$ 定义为：满足两点间最短路径经过 $x$ 的极远点对的数量。现给定树 $G$，求 $\sum\limits_{x \in G}{v_x^k}$ 对 $998244353$ 取模的值，其中 $k$ 是给定的常数，且 $k \in [1,2]$。 ## Input 第一行两个数 $n,k$，分别表示树 $G$ 的点数以及给定的常数。接下来 $n-1$ 行每行两个整数 $u,v$，表示点 $u$ 和点 $v$ 之间有一条边。 ## Output 输出一行一个整数，表示答案。 [samples] ## Background 没有什么距离是无法跨越的。 ## Note #### 样例解释 #1 $(1,2)$ 为极远点对，所以 $1$ 号和 $2$ 号点点权均为 $1$，$1^1 + 1^1 =2$。 ------------ #### 样例解释 #2 极远点对有 $(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$，故答案为 $4 \times 3^2 + 6^2 = 72$。 ------------ #### 数据范围 | 测试点编号 | $1$ | $2$ | $3$ | $4 \sim 5$ | $6$ | $7$ | $8 \sim 9$ | $10$ | | :----: | :----: | :----: | :----: | :----: | :----: | :----: | :----: | :----: | | $n$ | $300$ | $300$ | $2000$ | $2000$ | $10^5$ | $5 \times 10^6$ | $10^5$ | $5 \times 10^6$| | $k$ | $1$ | $2$ | $1$ | $2$ | $1$ | $1$ | $2$ | $2$ | 对于 $100\%$ 的数据，满足 $n \leq 5 \times 10^6$，$1 \leq k \leq 2$。 **本题输入量较大，请用较快的输入方法。**

Samples

Input #1

2 1
1 2

Output #1

Input #2

Output #2

API Response (JSON)

{
  "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 \\operatornam...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments