#P18136. Roars III
Roars III
Roars III
在一棵有 个顶点的树中,初始时某些顶点里有一只雄性吼叫蜗牛,每个顶点至多一只。
雌性蜗牛会出现在某个顶点并开始吼叫。只要存在能移动的雄性,每次吼叫会让其中恰好一只沿一条边移动到相邻顶点,并必须满足:
- 移动方向必须是朝向雌性所在顶点的方向;
- 目标顶点当前没有其他雄性蜗牛;
- 已经与雌性位于同一个顶点的雄性不能再移动;其他雄性可以移入尚未被雄性占据的雌性顶点。
当某次吼叫后没有任何雄性蜗牛能够移动时,雌性停止吼叫。雄性蜗牛的移动方式会选择使得吼叫次数最多。
请对每个可能的雌性位置,求出最多能够吼叫多少次。
没有雄性能够移动时过程结束;不能额外给答案加上一次“未引发移动”的吼叫。
输入格式
第一行包含整数 ()。
第二行包含一个长度为 的 0/1 串。若第 个字符为 1,则初始时第 个顶点有一只雄性蜗牛。
接下来 行,每行包含两个整数 ,表示一条树边。
输出格式
输出 个整数。第 个整数表示雌性位于第 个顶点时的最大吼叫次数。
样例
5
10101
1 2
2 3
2 4
4 5
2 2 2 3 3
初始树与雄性位置:

雌性位于 1 时,一种最优过程:

雌性位于 4 时,一种最优过程:
