CF575B Bribes

鲁里塔尼亚是一个道路网络维护极差的国家，这可不是什么好消息，因为货车司机常常需要送货。实际上，当道路被维护时，它们会变成单向道。结果，有时候按照规定从一个城镇到另一个城镇是无法到达的 —— 不过我们知道所有城镇都可以“违规”到达！ 幸运的是，警察非常腐败，只要司机“送点小礼物”，他们就允许逆行通过一条道路。每条道路上都有一辆巡逻车，每次司机逆行时，他们会收取 1000 鲁里塔尼亚第纳尔的贿赂。不过他们非常贪心，对同一名司机在同一条道路上的每一次逆行，都会要求上一次费用的两倍。 Borna 是一名货车司机，他琢磨透了这个贿赂规律。在工作中，他需要按照顺序在鲁里塔尼亚的 $K$ 个城镇做停靠。鲁里塔尼亚共有 $N$ 个城镇（编号为 $1$ 到 $N$），Borna 起始位于首都（即城镇 1）。他知道 $N-1$ 条道路中哪些目前是单向的，但他算不出自己至少需要多少贿赂警察的钱。请你帮助 Borna 计算他至少需要准备多少第纳尔用来贿赂警察。若你能帮他计算出来，你会获得丰厚的酬劳。

第一行包含一个整数 $N$，表示鲁里塔尼亚的城镇数。接下来的 $N-1$ 行，每行包含三个整数 $(a, b, x)$，表示一条连接城镇的道路。$a$ 和 $b$ 表示连通的两个城镇，$x$ 取值为 $0$ 或 $1$：$0$ 表示双向道路，$1$ 表示只有 $a→b$ 的方向可以合法通行。 接下来一行是一个整数 $K$，表示 Borna 需要停靠的城镇数。最后一行包含 $K$ 个正整数 $s_1, ..., s_K$，表示 Borna 需要按照顺序访问的城镇编号。 - $1 \leq N \leq 10^5$ - $1 \leq K \leq 10^6$ - $1 \leq a, b \leq N$，对于所有道路 - 所有道路的城市编号均符合条件 - $1 \leq s_i \leq N$，对于所有 $1 \leq i \leq K$

输出一个整数：Borna 至少需要准备的贿赂总额（以千为单位的鲁里塔尼亚第纳尔），对 $10^9+7$ 取模。

Borna 首次经过 $1→5$ 路线时需要支付 1000 第纳尔。接着他经过 $5→1→2→3→4$ 这段路径时不需要付钱。然而，他返回时的 $4→3→2→1→5$ 需要准备 3000（1000+2000）第纳尔。之后，他通过 $5→1→2$ 到 2 不用再付钱。最后，他要到达 2，只需待在原地，无需额外贿赂。因此总共需要准备 4000 第纳尔。 由 ChatGPT 5 翻译