A. 昔我往矣 - EOJ Monthly 2021.2 Sponsored by TuSimple

仪表盘所有提交榜单题解

单点时限: 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

Output

Input

Output

21
16

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

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

子任务 $3$ ，分值 $40$ 分，保证 $q \leq 100$

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

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

NaN

比赛状态发生变化，点 OK 刷新。

OK

EOJ Monthly 2021.2 Sponsored by TuSimple