luogu#P9440. [ICPC2021 WF] Dungeon Crawler

[ICPC2021 WF] Dungeon Crawler

题目描述

Alice and Bob are in charge of testing a new escape room! In this escape room, customers are trapped in a dungeon and have to explore the entire area. The dungeon consists of nn rooms connected by exactly n1n-1 corridors. It is possible to travel between any pair of rooms using these corridors.

Two of the dungeon rooms are special. One of these rooms contains a protective idol known as the "helix key´´. A different room contains a nasty "dome trap´´, which prevents the player from moving once activated. Entering the room with the trap before acquiring the key will result in the player being trapped in the dungeon forever. The player cannot start in the same room as the key or the trap.

There are qq different scenarios that Alice and Bob wish to examine. In the ithi^{th} scenario, the player starts in room sis_i, the key is in room kik_i, and the trap is in room tit_i. For each scenario, compute the minimum amount of time needed to explore the entire dungeon without getting trapped.

输入格式

The first line of input contains two integers nn and qq, where nn (3n20003 \leq n \leq 2000) is the number of rooms and qq (1q2000001 \leq q \leq 200000) is the number of scenarios to consider. Rooms are numbered from 11 to nn. The next n1n-1 lines each contain three integers uu, vv, and ww indicating that there is a corridor between rooms uu and vv (1u,vn,uv1 \leq u, v \leq n, u \neq v) that takes time ww (1w1091 \leq w \leq 10^9) to traverse.

Then follow qq lines: the ithi^{th} of these lines contains three distinct integers sis_i, kik_i, and tit_i (1si,ki,tin1 \leq s_i, k_i, t_i \leq n) indicating the room where the player starts, the room with the key, and the room with the trap, respectively.

输出格式

For each scenario, output the minimum amount of time needed to visit every room at least once. If it is impossible to visit every room at least once, output impossible\texttt{impossible}.

题目大意

题目描述

有一棵 nn 个结点的树,边带权。你可以从一个结点通过边移动到一个相邻的结点,花费等同于边权的时间。

其中,有两个特殊结点,一个结点里有钥匙,一个结点里有陷阱。你只有先获得钥匙,才能进入陷阱所在的结点。

现有 qq 组询问,在第 ii 组询问中,你要从第 sis_i 号结点出发,钥匙在第 kik_i 号结点,陷阱在第 tit_i 号结点。你需要对于每组询问回答遍历整棵树所需的最短时间。题目保证你不会在钥匙所在的结点或者陷阱所在的结点出发。如果不可能遍历整棵树,输出 impossible

输入格式

第一行两个整数 n,qn,q,含义如题目所述。

接下来 n1n-1 行,每行三个整数 u,v,wu,v,w,表示有一条连接结点 u,vu,v,权值为 ww 的边。

接下来 qq 行,每行三个整数 si,ki,tis_i,k_i,t_i,含义如题目所述。

3n20003\le n\le 20001q2×1051\le q \le 2\times10^51u,vn,uv1\le u,v\le n,u\ne v1w1091\le w\le 10^91si,ki,tin1\le s_i,k_i,t_i\le n

输出格式

对于每组询问,输出一行,包含一个整数表示答案,或者输出 impossible 表示无解。

5 4
1 2 3
1 3 1
3 4 4
3 5 2
1 2 4
1 4 2
5 2 1
4 3 1

15
17
impossible
12

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

11
impossible
10
10