| 题目名称 | 936. [河南省队2012] 座位问题 |
|---|---|
| 输入输出 | seat.in/out |
| 难度等级 | ★ |
| 时间限制 | 100 ms (0.1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 wo shi 刘畅
于2012-07-17加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：18， 提交：67， 通过率：26.87% | ||||
 0 |
100 | 0.156 s | 4.12 MiB | C++ |
 wo shi 刘畅 |
100 | 0.160 s | 3.13 MiB | C++ |
 0 |
100 | 0.161 s | 3.67 MiB | C++ |
|
0 |
100 | 0.166 s | 3.44 MiB | C++ |
 zys |
100 | 0.190 s | 3.44 MiB | C++ |
 forever |
100 | 0.195 s | 6.11 MiB | C++ |
|
0 |
100 | 0.198 s | 4.58 MiB | C++ |
 ImwaOuKur |
100 | 0.198 s | 4.89 MiB | C++ |
|
ImwaOuKur |
100 | 0.225 s | 4.40 MiB | C++ |
 _stranger |
100 | 0.228 s | 23.20 MiB | C++ |
| 本题关联比赛 | |||
| 20120718 | |||
| 关于 座位问题 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @啊啦吧啦吧啦 :
这个题本来就是这样 forever
2015-10-30 17:29
6楼
| ||||
|
回复 @<蒟蒻>我要喝豆奶 :
真正评测的时候时间限制至少1s 0
2015-10-30 17:28
5楼
| ||||
|
看看谁不开优化开关可以过
| ||||
|
真正评测时候都不开O2
 <蒟蒻>我要喝豆奶
2015-10-30 17:21
3楼
| ||||
|
暴力都a，正解t了
| ||||
|
蒟蒻写的线段树居然还不如暴力……是在下输了啊，居然连一条链的数据都没有……
| ||||
真红之蝶
devil-
问题描述：
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;