Bribes

题意翻译

给一张包含 $N$ 个结点的树。 在树上，对于有些边 $(a,b)$，$a→b$ 和 $b→a$ 都无需花费，我们称这种边为无向边；对于另一些边，$a→b$ 无需花费，而 $b→a$ 需要花费，且第 $i$ 次从 $b$ 到 $a$ 时花费为 $2^{i-1}$，我们将这种边称为有向边。 给你一个长度为 $K$ 的数列 $s_1, s_2,\dots, s_K$，你要从结点 $s_1$ 前往 $s_2$，再从 $s_2$ 去往 $s_3$……一直到 $s_K$。 试求最小的花费 $\bmod (10^9+7)$。 ### 输入格式 第一行，一个整数 $N$。 接下来的 $N-1$ 行，每行三个整数 $a,b,x$， - 如果 $x=0$，边 $(a,b)$ 为无向边； - 如果 $x=1$，边 $(a,b)$ 为有向边。 第 $N+1$ 行，一个整数 $K$。 下一行，$K$ 个整数 $s_1, s_2, \dots, s_K$。 ### 样例说明 $1 → 5$，路径上总花费为 1。 $5 → 1 → 2 → 3 → 4$，路径上无花费。 $4 → 3 → 2 → 1 → 5$，路径上总花费为 3。 $5 → 1 → 2$，路径上无花费。

题目描述

Ruritania is a country with a very badly maintained road network, which is not exactly good news for lorry drivers that constantly have to do deliveries. In fact, when roads are maintained, they become one-way. It turns out that it is sometimes impossible to get from one town to another in a legal way – however, we know that all towns are reachable, though illegally! Fortunately for us, the police tend to be very corrupt and they will allow a lorry driver to break the rules and drive in the wrong direction provided they receive ‘a small gift’. There is one patrol car for every road and they will request 1000 Ruritanian dinars when a driver drives in the wrong direction. However, being greedy, every time a patrol car notices the same driver breaking the rule, they will charge double the amount of money they requested the previous time on that particular road. Borna is a lorry driver that managed to figure out this bribing pattern. As part of his job, he has to make $ K $ stops in some towns all over Ruritania and he has to make these stops in a certain order. There are $ N $ towns (enumerated from 1 to $ N $ ) in Ruritania and Borna’s initial location is the capital city i.e. town 1. He happens to know which ones out of the $ N-1 $ roads in Ruritania are currently unidirectional, but he is unable to compute the least amount of money he needs to prepare for bribing the police. Help Borna by providing him with an answer and you will be richly rewarded.

输入输出格式

输入格式

The first line contains $ N $ , the number of towns in Ruritania. The following $ N-1 $ lines contain information regarding individual roads between towns. A road is represented by a tuple of integers ( $ a $ , $ b $ , $ x $ ), which are separated with a single whitespace character. The numbers $ a $ and $ b $ represent the cities connected by this particular road, and x is either 0 or 1: 0 means that the road is bidirectional, 1 means that only the $ a→b $ direction is legal. The next line contains $ K $ , the number of stops Borna has to make. The final line of input contains K positive integers $ s_{1},…,s_{K} $ : the towns Borna has to visit. - $ 1<=N<=10^{5} $ - $ 1<=K<=10^{6} $ - $ 1<=a,b<=N $ for all roads -  for all roads - $ 1<=s_{i}<=N $ for all $ 1<=i<=K $

输出格式

The output should contain a single number: the least amount of thousands of Ruritanian dinars Borna should allocate for bribes, modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

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

输出样例 #1

4

说明

Borna first takes the route $ 1→5 $ and has to pay 1000 dinars. After that, he takes the route $ 5→1→2→3→4 $ and pays nothing this time. However, when he has to return via $ 4→3→2→1→5 $ , he needs to prepare 3000 (1000+2000) dinars. Afterwards, getting to 2 via $ 5→1→2 $ will cost him nothing. Finally, he doesn't even have to leave town 2 to get to 2, so there is no need to prepare any additional bribe money. Hence he has to prepare 4000 dinars in total.