网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[河南省队2012]座位问题
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | seat.in | 输出文件 | seat.out |
问题描述:
ZhouH电影院有一个很特别的地方在于这个电影院里的座位的布置是树形的,座位按1~n编号,1号座位最靠近门口,即每个人进入影院都会先经过1号座位,现恰有n个人依次来看电影,分别按先后顺序标号为1~n,影院门口一开始会给出n个数,每个数x表示如果你是第i个来的人就必须坐x号这个座位,每当有人进来看电影的时候,都会从进入1号座位开始,走一条最短的路,到达自己要坐的座位,但是如果经过的路程里某个座位已经坐了人的话,会打扰到他,所以请依次求出每个人依次进入电影院会打扰到的人的个数。
输入格式:
第一行一个数n,表示有n个座位和n个人。
接下来n-1行每行两个数i,j,表示i号座位与j号相连,当然边是双向的。
第n+1到第n+n+1行:每行一个数x,表示第i-n个来的人应该坐x号位置,如样例输入中:
第6行中的4表示,第1个来的人应该坐4号座位。
第7行中的2表示,第2个来的人应该坐2号座位。
第8行中的1表示,第3个来的人应该坐1号座位。
第9行中的5表示,第4个来的人应该坐5号座位。
第10行中的3表示,第5个来的人应该坐3号座位。
样例输入:
5
1 4
5 4
1 3
2 4
4
2
1
5
3
样例输出:
0
1
0
2
1
样例输出解释:
第一个人进电影院,他必须坐4号,从1号座位到4号座位路径上的座位都是空的,因为他是第一个来的,所以输出0。
第二个人进电影院,他必须坐2号,从1号座位到2号座位路径上会经过4号座位,4号座位上有人,所以输出1。
第三个人进电影院,他必须坐1号,直接做,所以输出0。
第四个人进电影院,他必须坐5号,从1号座位到5号座位路径上会经过1号座位和4号座位,打扰到两人,所以输出2。
第五个人进电影院,他必须坐3号,从1号座位到3号座位路径上会经过1号座位,1号座位上有人,所以输出1。
数据范围:
对于50%的数据,1<=n<=5000.
对于100%的数据,1<=n<=100000;
ZhouH电影院有一个很特别的地方在于这个电影院里的座位的布置是树形的,座位按1~n编号,1号座位最靠近门口,即每个人进入影院都会先经过1号座位,现恰有n个人依次来看电影,分别按先后顺序标号为1~n,影院门口一开始会给出n个数,每个数x表示如果你是第i个来的人就必须坐x号这个座位,每当有人进来看电影的时候,都会从进入1号座位开始,走一条最短的路,到达自己要坐的座位,但是如果经过的路程里某个座位已经坐了人的话,会打扰到他,所以请依次求出每个人依次进入电影院会打扰到的人的个数。
输入格式:
第一行一个数n,表示有n个座位和n个人。
接下来n-1行每行两个数i,j,表示i号座位与j号相连,当然边是双向的。
第n+1到第n+n+1行:每行一个数x,表示第i-n个来的人应该坐x号位置,如样例输入中:
第6行中的4表示,第1个来的人应该坐4号座位。
第7行中的2表示,第2个来的人应该坐2号座位。
第8行中的1表示,第3个来的人应该坐1号座位。
第9行中的5表示,第4个来的人应该坐5号座位。
第10行中的3表示,第5个来的人应该坐3号座位。
样例输入:
5
1 4
5 4
1 3
2 4
4
2
1
5
3
样例输出:
0
1
0
2
1
样例输出解释:
第一个人进电影院,他必须坐4号,从1号座位到4号座位路径上的座位都是空的,因为他是第一个来的,所以输出0。
第二个人进电影院,他必须坐2号,从1号座位到2号座位路径上会经过4号座位,4号座位上有人,所以输出1。
第三个人进电影院,他必须坐1号,直接做,所以输出0。
第四个人进电影院,他必须坐5号,从1号座位到5号座位路径上会经过1号座位和4号座位,打扰到两人,所以输出2。
第五个人进电影院,他必须坐3号,从1号座位到3号座位路径上会经过1号座位,1号座位上有人,所以输出1。
数据范围:
对于50%的数据,1<=n<=5000.
对于100%的数据,1<=n<=100000;