题目描述

在一个奇怪的国家中，有 $N$ 个城市，编号为 $0$ 到 $N-1$。城市之间有 $N-1$ 条双向道路，每条道路有长度，并保证任意两个城市之间都能通过道路互相到达。因此城市与道路构成一棵带权树。

这个国家有 $N$ 家袜子工厂，每个城市恰好有一家。由于这个国家很奇怪，每家工厂每天可能只生产左袜子，也可能只生产右袜子，也可能当天不工作。

Martin 每天从当地报纸得知，哪些工作的工厂生产左袜子，哪些工作的工厂生产右袜子。形式化地，对每一天，他会得到两个城市列表：

• $X_0,X_1,\ldots,X_{S-1}$：生产左袜子的城市；
• $Y_0,Y_1,\ldots,Y_{T-1}$：生产右袜子的城市。

有些城市可以不出现在任何一个列表中。

对于每一天，Martin 想知道从一个生产左袜子的城市到一个生产右袜子的城市的最短距离，这样他可以买到一双袜子且走得尽可能少。

任务

给定国家的道路结构，请实现程序 factories，回答 $Q$ 个上述查询。

实现要求

你需要实现以下两个函数：

void Init(int N, int A[], int B[], int D[]);

该函数在每个测试开始时调用一次，给出城市数 $N$ 以及三个长度为 $N-1$ 的数组。对于每个 $0\le i\le N-2$，城市 $A[i]$ 与城市 $B[i]$ 之间有一条长度为 $D[i]$ 的道路。

long long Query(int S, int X[], int T, int Y[]);

该函数对每个查询调用一次。$S,T$ 分别表示两个列表的长度。数组 $X[0],\ldots,X[S-1]$ 与 $Y[0],\ldots,Y[T-1]$ 分别表示生产左袜子和右袜子的城市编号。

函数需要返回一个城市来自第一个列表、另一个城市来自第二个列表时的最小树上距离。

你的程序 factories.cpp 必须实现上述两个函数，可以包含辅助代码，但不能包含 main，不能读标准输入，也不能向标准输出输出。需要包含头文件：

#include "factories.h"

数据范围

• $2 \le N \le 500000$
• $1 \le Q \le 100000$
• $0 \le A_i,B_i \le N-1$，$A_i\ne B_i$
• $1 \le D_i \le 10^8$
• $1 \le S,T \le N-1$
• $0 \le X_i,Y_j \le N-1$
• 同一次查询中，$X_0,\ldots,X_{S-1},Y_0,\ldots,Y_{T-1}$ 两两不同
• 所有查询的 $S$ 之和不超过 $10^6$
• 所有查询的 $T$ 之和不超过 $10^6$

本地测试格式

提供文件 Lgrader.cpp 用于本地测试。

本地测试输入格式如下：

第一行输入 $N,Q$。

接下来 $N-1$ 行，每行三个整数 $A_i,B_i,D_i$，表示一条道路。

随后每个查询占三行：

1. 第一行输入 $S,T$；
2. 第二行输入 $X_0,\ldots,X_{S-1}$；
3. 第三行输入 $Y_0,\ldots,Y_{T-1}$。

本地 grader 会输出每个查询返回的答案，或在出现问题时输出错误信息。

子任务

只有通过某子任务及其所有依赖子任务的全部测试，才能获得该子任务分数。

样例

输入

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

输出

12
3
11

说明

第一组查询中，第一个列表为城市 $0,6$，第二个列表为城市 $3,4$。四种配对距离分别为：

• $dist(0,3)=13$
• $dist(0,4)=14$
• $dist(6,3)=12$
• $dist(6,4)=13$

最小值为 $12$。

第二组查询的最小距离为城市 $1$ 与城市 $6$ 之间的距离，等于 $3$。

第三组查询两个列表各有一个城市，二者距离为 $11$。