染色游戏

题目描述 Alice 和 Bob 在玩游戏。有一棵𝑛𝑛个点，𝑛𝑛 − 1条边的树，每条边有边权，一开始所 有边都是白色的。

当游戏开始的时候，Alice 和 Bob 各自会选择一个点作为起始点。每一轮 Alice 先 开始移动，然后 Bob 移动。Alice 会选择和当前点相连的一条白色或者红色的边， 把它染成红色，然后移动到另一端。Bob 会选择和当前点相连的白色或蓝色的边， 然后染成蓝色，移动到另一端。当所有边被染成红色或者蓝色时游戏结束。

Alice 想要最大化红色边的边权和，Bob 想要最大化蓝色边的边权和，两边都按最 优策略操作，最后 Alice 和 Bob 的边权和分别是多少？

你需要对𝑚𝑚组初始状态回答，每组初始状态之间的游戏都是独立的，也就是从全是 白的局面开始。

输入格式 第一行，包含两个整数𝑛𝑛, 𝑚𝑚。

接下来𝑛𝑛 − 1行，每行包含三个整数𝑢𝑢, 𝑣𝑣, 𝑤𝑤，表示一条边的端点和边权。

接下来𝑚𝑚行，每行两个整数𝑎𝑎, 𝑏𝑏，表示 Alice 和 Bob 的起始点。

输出格式 𝑚𝑚行，每行一个整数，表示 Alice 的最大边权和。

样例输入 1 3 3 1 2 3 1 3 1 1 1 1 2 3 1

样例输出 1 3 4 1

样例输入输出 2 见下发文件。 数据规模 共 10 组数据。

测试点1,2满足𝑛𝑛 ≤ 15。

测试点3,4,5满足𝑛𝑛, 𝑚𝑚 ≤ 1000。

测试点6,7满足树是一条链。

对于所有数据，满足1 ≤ 𝑛𝑛, 𝑚𝑚 ≤ 105 , 1 ≤ 𝑤𝑤 ≤ 1000。