#P18796. [Omi2022] 交通网络

[Omi2022] 交通网络

[Omi2022] 交通网络

题目描述

一座城市的交通网络是一棵有 NN 个顶点的带权树。顶点编号为 11 到 NN,每条边的权值表示对应道路的长度,道路可以双向通行。

以顶点 11 为根。顶点 BB 的管理区域定义为以 BB 为根的整棵子树,包括 BB 自己。

一个区域内的路线是一条完全位于该区域内的简单路径,即不能重复经过任何顶点。路线长度等于路径上所有边权之和。允许只包含一个顶点,此时长度为 00。

你需要回答 QQ 次询问。每次询问给出两个顶点 A,BA,B,保证 AA 位于 BB 的子树内。求:完全位于 BB 的子树内,并且经过顶点 AA 的最长简单路径的长度。

顶点 AA 可以是路径的端点,也可以是内部顶点。

输入格式

第一行包含两个整数 N,QN,Q。

接下来 N−1N-1 行,每行包含三个整数 u,v,wu,v,w,表示顶点 u,vu,v 之间有一条长度为 ww 的道路。保证这些道路构成一棵树。

接下来 QQ 行,每行包含两个整数 A,BA,B,表示一次询问。注意输入顺序是先给必须经过的顶点 AA,再给限定子树的根 BB。

输出格式

输出 QQ 行,每行一个整数,表示对应询问的答案。

答案可能超过 32 位有符号整数的范围。

样例输入

10 3
1 2 2
1 3 5
1 4 3
2 5 3
5 6 1
7 5 2
8 6 3
6 9 8
10 8 4
6 2
7 1
6 1

样例输出

15
12
19

数据范围与分组

  • 1≤N,Q≤1051\le N,Q\le10^5;
  • 1≤u,v,A,B≤N1\le u,v,A,B\le N;
  • 1≤w≤1061\le w\le10^6;
  • 对每次询问,BB 是 AA 的祖先或 A=BA=B。
分值 额外限制
10 树是一条链,顶点 ii 为顶点 i+1i+1 的父亲,且所有边权为 11
根节点与其余所有节点直接相连,且所有边权为 11
15 N,Q≤1000N,Q\le1000
所有询问满足 A=BA=B
N,Q≤50000N,Q\le50000
35 无额外限制