[R33F]最大边权 - 代码源竞赛平台

时空限制

2S/512M

题目描述

给定一棵 $n$ 个节点的树，节点编号为 $1 \sim n$，每条边有正整数边权。

进行 $Q$ 次独立询问。每次询问给出 $k$ 个区间 $[l_1, r_1], \ldots, [l_k, r_k]$。

定义点集

$$V = \{ x \mid \exists j \in [1,k],\ l_j \le x \le r_j \}$$

即 $V$ 为所有节点编号落在任一区间内的点的集合。

考虑 $V$ 中所有无序点对 $(u,v) (u \ne v)$，将树上 $u$ 到 $v$ 的简单路径上的每条边染色。

询问的答案为所有被染色边的最大边权。若 $|V| < 2$，输出 $0$。

格式

输入格式

第一行包含两个整数 $n, Q$，表示节点数和询问次数。

接下来 $n-1$ 行，每行三个整数 $u, v, w$，表示节点 $u$ 和 $v$ 之间有一条权值为 $w$ 的边。

接下来是 $Q$ 次询问的描述。对于每次询问：

第一行包含一个整数 $k_i$，表示第 $i$ 次询问的区间数量。

接下来 $k_i$ 行，每行包含两个整数 $l_j, r_j$，表示一个区间。

输出格式

对于每次询问，输出一行，包含一个整数，表示该次询问的答案。

样例

样例输入 #1

10 5
1 2 100
2 3 50
2 4 200
1 5 150
5 6 20
5 7 80
7 8 250
7 9 90
9 10 400
2
8 8
10 10
2
3 3
8 8
1
3 4
2
3 3
6 6
1
1 1

样例输出 #1

400
250
200
150
0

数据规模

对于 $40\%$ 的数据，$1 \leq n , q \leq 1000$。

对于 $100\%$ 的数据，$1 \leq n, q \leq 2 \times 10^5$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^9$，$1 \leq \sum k_i \leq 2 \times 10^5$，$1 \leq l_j \leq r_j \leq n$。