#P18717. Discount Event

    ID: 18053 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-树直径树形 DP换根 DPLCA树上倍增幺半群区间聚合

Discount Event

Discount Event

某国有 nn 座城市和 n−1n-1 条道路。城市编号为 11 到 nn,道路编号为 11 到 n−1n-1。第 ii 条道路双向连接城市 ai,bia_i,b_i,通行费用为 wiw_i。任意两座城市之间都可以通过这些道路到达。

两座城市的距离定义为从一座城市前往另一座城市所需的最小费用。

作为道路公司的总裁,你准备在节日期间举办优惠活动,一共有 qq 个方案。第 ii 个方案把城市 xix_i 与 yiy_i 之间最短路径上的所有道路费用改为 00。请分别计算每个方案实施后,任意两座城市之间距离的最大值。

各方案独立,均基于原始道路费用计算;一个方案的修改不会保留到下一个方案。

输入格式

第一行一个整数 nn,2≤n≤1052\le n\le10^5。

接下来 n−1n-1 行,第 ii 行三个整数 ai,bi,wia_i,b_i,w_i:

$$1\le a_i,b_i\le n,\quad a_i\ne b_i,\quad1\le w_i\le10^9.$$

保证任意两座城市可以互相到达。因此给出的道路构成一棵树,两点之间的路径唯一。

下一行一个整数 qq,1≤q≤1051\le q\le10^5。

接下来 qq 行,每行两个整数 xi,yix_i,y_i,1≤xi,yi≤n1\le x_i,y_i\le n,且 xi≠yix_i\ne y_i。

输出格式

输出 qq 行,第 ii 行一个整数,表示第 ii 个方案实施后的最大城市间距离。

完整原样例

5
1 2 1
1 3 2
2 4 4
2 5 2
3
1 4
3 5
5 4
4
4
3
5
1 2 2
1 3 3
1 4 5
1 5 4
3
1 2
1 4
4 5
9
7
5
8
1 2 3
1 3 5
2 4 5
2 5 3
2 6 6
6 7 1
6 8 2
7
1 2
1 3
2 4
2 5
2 6
6 7
6 8
13
13
16
16
13
16
15
7
1 2 3
1 3 4
2 4 2
2 5 1
3 6 6
3 7 2
6
1 2
1 3
1 4
1 5
1 6
1 7
12
11
11
12
7
11