题目描述

给定一棵 $n$ 个结点的无根树，边有边权。

给出 $m$ 次询问，每个询问给出两个数 $k,x$，表示你需要选择恰好 $k$ 条简单路径，满足：

• 至少有一条路径经过编号为 $x$ 的点

• 这 $k$ 条路径所包含的边的权值和尽可能大（每条边的权值只算一次）。

你的任务即对每个询问给出可能的最大边权和，保证答案在 $\texttt{int}$ 范围之内。

输入格式

第一行二个整数 $n,m$，表示结点数和询问次数。

接下来 $(n-1)$ 行，每行三个整数 $u,v,w$，描述一条边权为 $w$ 的，连接 $u$ 和 $v$ 的边。

接下来 $m$ 行，每行两个整数 $k,x$，表示一组询问。

输出格式

对于每组询问，输出一行一个整数，表示答案。

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

14
13
17

提示

对于 $100\%$ 的数据，$1\le n,m\le 10^5$。

题目来源

没有写明来源