← 返回比赛

已结束贝加尔国际运算编程大赛校内选拔赛(公开赛)

← 上一题下一题 →

A4592 | $巡查$

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

时间限制:2000ms 空间限制:512MB 我们的小X在统治着一大片星系，这片星系由$n$ 个星球组成，这$n$ 个星球之间建立空间传送站，一共有$n-1$ 对空间传送站让这$n$ 个星球相互之间都可以连通。到这里你应该知道，通过这$n-1$ 个传送站，$n$ 个星球的连通关系组成了一颗树。 现在小X要对星系进行巡查，他给定了长度为 $m$的巡查星球顺序的序列 $c_1,c_2...c_m$，他要求必须严格按照这个顺序来巡查整个星系，且他的巡查分为了$m$轮。 小X的大本营在$1$号星球，对于第$i$轮巡查，小X从$1$号星球出发，最终巡查的终点在$c_i$号星球，但是他还要顺带着必须经过 编号为$c_1,c_2...c_{i-1}$的星球，当然，顺带经过的这些编号为$c_1,c_2...c_{i-1}$星球，不需要按照序列给定的顺序经过。 现在小X想知道，对于每轮巡查，他最少需要经过空间传送的次数是多少？

输入格式

第一行两个正整数 $n,m$ 接下来 $n-1$ 行，每行两个正整数 $x,y$，表示一个空间传送站，让 $(x,y)$ 这两颗星球可以直接传送。 接下来一行有 $m$ 个正整数，表示 $c_1,c_2...c_m$

输出格式

输出 $m$ 行，第 $i$ 行一个非负整数，表示题目中对第 $i$ 轮巡查，最少需要经过空间传送的次数。

输入输出样例

输入 #1

输出 #1

2
4
6

C++ 编辑器

输入

输出