4116. 昔我往矣

单点时限: 1.0 sec

内存限制: 512 MB

在背诵《诗经》的时候,小 G 回忆起了一棵树。树上有 $5$ 个人,他们站在互不相同的节点上。

小 G 想去拜访他们,她会从某个人所在的节点出发,沿树上最短路径走向下一个人,以此类推,直到拜访完这 $5$ 个人。

树上的所有边还未被翻新,翻新一条边需要一定的代价(边是双向的),而小 G 只愿意走被翻新过的边。她想知道,为了使得无论顺序如何都可以拜访完 $5$ 个人,最小需要的翻新代价之和是多少。

输入格式

第一行,一个正整数 $n$,表示节点个数。

接下来 $n-1$ 行,每行 $3$ 个整数 $u,v,w$,表示 $u$ 和 $v$ 之间有一条边权为 $w$ 的边。点的编号从 $0$ 到 $n-1$,保证构成的是一棵树。

接下来一行,一个正整数 $q$,表示询问次数。

接下来 $q$ 行,每行 $5$ 个正整数 $a,b,c,d,e$,表示 $5$ 个人所在的节点编号,保证它们互不相同。

输出格式

共 $q$ 行,依次对应询问答案。

样例

Input
5
0 1 1
1 2 2
2 3 3
3 4 4
1
4 0 3 1 2
Output
10
Input
6
4 0 4
0 1 2
1 3 9
3 5 1
3 2 5
2
4 0 3 5 2
0 4 1 3 5
Output
21
16

提示

子任务 $1$,分值 $7$ 分,保证 $n=5,q=1$

子任务 $2$,分值 $23$ 分,保证任意节点度数 $\le 2$

子任务 $3$,分值 $40$ 分,保证 $q\le 100$

子任务 $4$,分值 $30$ 分,无特殊限制

对于所有数据,$5\le n\le 50000$,$1\le q \le 10000$,$1\le w\le 1000$

159 人解决,502 人已尝试。

194 份提交通过,共有 1793 份提交。

5.2 EMB 奖励。

创建: 3 月,2 周前.

修改: 3 月,2 周前.

最后提交: 1 周前.

来源: N/A

题目标签