A91411.商务旅行
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
某地首都的商人要经常到其他城镇去做生意,他们会按自己的路线去走。
有 N 个城镇,首都编号为 1。商人从首都出发,其他各城镇之间都有道路连接。
任意两个城镇之间如果有直连道路,在他们之间行驶需要花费单位时间。如果从首都出发,能到达任意一个城镇。
请你求出商人最短的旅行时间。
输入格式
第一行有一个整数 N,为城镇的数目。
接下来 N−1 行,每行两个整数 a 和 b,表示城镇 a 和城镇 b 有公路连接。
接下来一个整数 M,然后 M 行,每行有该商人需要顺次经过的各城镇编号。
输出格式
一行,输出商人最短的旅行时间。
输入输出样例
输入#1
5 1 2 1 5 3 5 4 5 4 1 3 2 5
输出#1
7
说明/提示
数据范围:1≤N≤30000。保证公路网络不会存在环。