树上信标（beacon）

题目描述

$\text{DAMON THRONE}$ 在一片训练区中布置了 $n$ 个信标点。

这些信标点由 $n-1$ 条道路连接，任意两个信标点之间都可以互相到达，并且不存在环。也就是说，这些道路构成一棵树。

第 $i$ 条道路连接信标点 $u_i$ 和 $v_i$，长度为 $w_i$，现在有 $q$ 次询问，每次给出两个信标点 $x,y$。

对于每次询问，请你输出：

1. 从 $x$ 到 $y$ 的路径总长度；
2. 从 $x$ 到 $y$ 的路径上，最长的一条道路长度。

输入格式

第一行包含两个整数 $n,q$，表示信标点数量和询问次数。

接下来 $n-1$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示一条道路。

接下来 $q$ 行，每行包含两个整数 $x,y$，表示一次询问。

输出格式

对于每次询问，输出一行两个整数，分别表示：

• 路径总长度；
• 路径上的最大边权。

输入输出样例 #1

输入 #1

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

输出 #1

9 5
18 7
8 7
0 0

样例解释 #1

对于第一个询问 $4,5$：

路径为：

$$4\to2\to5$$

路径总长度为：

$$5+4=9$$

最大边权为 $5$。

对于第二个询问 $4,7$：

路径为：

$$4\to2\to1\to3\to6\to7$$

路径总长度为：

$$5+3+2+7+1=18$$

最大边权为 $7$。

最后一组询问 $1,1$ 时，起点和终点相同，路径长度为 $0$，最大边权也记为 $0$。

输入输出样例 #2

输入 #2

5 3
1 2 10
2 3 20
3 4 30
4 5 40
1 5
2 4
3 3

输出 #2

100 40
50 30
0 0

数据范围与约定

对于所有测试数据，保证：

$$1 \le n,q \le 2\times 10^5,\quad 1 \le u_i,v_i,x,y \le n,\quad 1 \le w_i \le 10^9 $$

并保证输入的 $n-1$ 条道路构成一棵树。

测试点	分值	$n$	$q$	$w_i$	特殊性质
$1\sim 2$	$10$	$\le 200$		$\le 10^3$	无
$3\sim 4$	$20$	$\le 2000$		$\le 10^9$	$\text{A}$
$5\sim 6$		$\le 10^5$			$\text{B}$
$7\sim 8$		$\le 2\times10^5$			$\text{C}$
$9\sim 10$	$30$				无

特殊性质 $\text{A}$：保证树是一条链，即第 $i$ 条边连接 $i$ 和 $i+1$。

特殊性质 $\text{B}$：保证所有询问中都有 $x=1$。

特殊性质 $\text{C}$：保证所有边权相同。