×

计蒜客

  1. 题库
  2. 多项式
  3. 问答
  • 50.59%
  • 131072K

题目描述

码队现在给你一棵树,这棵树的每条边都有该边的权值。我们定义:一条路径的权值等于该路径上所有边权之和的 $k$ 次方

现在,码队请你求出:在该树中随机选择一条路径,其路径权值的期望。答案对 $998244353$ 取模。

随机方式为:随机从 $[1..n]$ 等概率选出一个数字 $s$ 作为起点,再随机从 $[1..n]$ 等概率选出一个数字 $t$ 作为终点,$s,t$ 可以相同;

输入格式

输入数据共包含 $n$ 行。

第一行为两个正整数 $n, k$,表示树结点个数和幂次。

接下来的 $n-1$ 行,每行为三个正整数 $x,y,z$ ,以空格分隔,表示该树中有一条从 $x$ 到 $y$ ,权值为 $z$ 的边。

输出格式

输出数据仅一行,包含一个数值,即在该树中随机选择一条路径,其路径权值的期望。

数据范围

  • $n \le 10^5, k \le 13$
  • $1 \le x, y \le n, 1 \le z \le 10^5$

输出时每行末尾的多余空格,不影响答案正确性

样例输入

6 2
2 1 2
4 1 2
6 5 3
3 6 1
6 4 2

样例输出

443664176

想挑战这道题吗

  • main.c