编号 题目名称 状态 分数 总时间 内存 代码 提交者 提交时间
#151 #8. 迷宫 Accepted 100 484 ms 22076 K C++ / 1.7 K Sengxian 2016-11-14 15:37:55
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 100000 + 3;
vector<int> G[MAX_N];
int n, q, rnk[MAX_N], lst[MAX_N];
bool block[MAX_N];

int s[MAX_N], dfn[MAX_N], dep[MAX_N], ancestor[20][MAX_N];
void dfs(int u, int fa = -1) {
	static int tsp1 = 0, tsp2 = 0;
	dfn[u] = tsp1++, s[u] = 1;
	for (int i = 0; i < (int)G[u].size(); ++i) if (G[u][i] != fa) {
		ancestor[0][G[u][i]] = u;
		dep[G[u][i]] = dep[u] + 1;
		dfs(G[u][i], u);
		s[u] += s[G[u][i]];
	}
	lst[tsp2] = u;
	rnk[u] = tsp2++;
}

void process() {
	for (int w = 1; (1 << w) < n; ++w)
		for (int i = 0; i < n; ++i)
			if (dep[i] - (1 << w) >= 0)
				ancestor[w][i] = ancestor[w - 1][ancestor[w - 1][i]];
}

priority_queue<int, vector<int>, greater<int> > pq;

void insert(int x) {
	while (x--) {
		assert(!pq.empty());
		int u = lst[pq.top()]; pq.pop();
		block[u] = true;
		if (x == 0) printf("%d\n", u + 1);
	}
}

void query(int u) {
	int t = u;
	for (int w = log2(dep[u]); w >= 0; --w)
		if (dep[u] - (1 << w) >= 0 && block[ancestor[w][u]]) u = ancestor[w][u];
	pq.push(rnk[u]);
	block[u] = false;
	printf("%d\n", dep[t] - dep[u]);
}

int main() {
	freopen("puzzle.in", "r", stdin);
	freopen("puzzle.out", "w", stdout);
	scanf("%d%d", &n, &q);
	for (int i = 0, u, v; i < n - 1; ++i) {
		scanf("%d%d", &u, &v), --u, --v;
		G[u].push_back(v), G[v].push_back(u);
	}
	for (int i = 0; i < n; ++i) sort(G[i].begin(), G[i].end());
	dfs(0), process();
	
	for (int i = 0; i < n; ++i) pq.push(i);
	while (q--) {
		int type, x;
		scanf("%d%d", &type, &x);
		if (type == 1) {
			insert(x);
		} else if (type == 2) {
			query(x - 1);
		}
	}
	return 0;
}
测试点 #1
Accepted
得分:100
用时:2 ms
内存:22076 KiB

输入文件

100 100
1 2
1 3
2 4
2 5
4 6
6 7
6 8
2 9
7 10
6 11
4 12
10 13
6 14
7 15
9 16
8 17
17 18
9 19
2 20
6 21
21 22
22 23
13 24
...
期望输出
72
22
4
45
32
1
1
3
78
2
93
4
3
4
1
1
3
0
3
3
6
3
4
1
9
1
5
1
6
3
3
4
2
1
3
6
1
7
1
6
5
1
2
1
6
1
8
1
6
2
0
26
3
0
37
5
...
你的输出
72
22
4
45
32
1
1
3
78
2
93
4
3
4
1
1
3
0
3
3
6
3
4
1
9
1
5
1
6
3
3
4
2
1
3
6
1
7
1
6
5
1
2
1
6
1
8
1
6
2
0
26
3
0
37
5
...

测试点 #2
Accepted
得分:100
用时:2 ms
内存:22076 KiB

输入文件

100 100
1 2
1 3
2 4
4 5
4 6
3 7
1 8
4 9
1 10
9 11
4 12
5 13
7 14
13 15
13 16
15 17
11 18
2 19
3 20
13 21
15 22
21 23
14 ...
期望输出
82
6
97
94
49
38
4
1
6
5
1
4
1
2
5
1
1
3
1
3
2
1
2
6
2
7
4
2
3
3
3
3
2
1
2
1
7
2
1
8
1
2
3
1
4
5
1
2
3
2
1
6
1
2
5
1
2
1...
你的输出
82
6
97
94
49
38
4
1
6
5
1
4
1
2
5
1
1
3
1
3
2
1
2
6
2
7
4
2
3
3
3
3
2
1
2
1
7
2
1
8
1
2
3
1
4
5
1
2
3
2
1
6
1
2
5
1
2
1...

测试点 #3
Accepted
得分:100
用时:2 ms
内存:22076 KiB

输入文件

100 100
1 2
1 3
3 4
3 5
4 6
5 7
1 8
7 9
1 10
5 11
9 12
5 13
3 14
9 15
1 16
2 17
3 18
10 19
10 20
13 21
1 22
16 23
5 24
4...
期望输出
48
1
2
2
1
3
16
1
3
1
4
3
3
0
1
2
1
6
2
1
3
10
1
1
5
2
1
5
1
3
1
3
2
3
3
3
1
2
1
6
1
5
1
1
1
6
3
5
2
1
3
0
2
4
20
1
5
1
...
你的输出
48
1
2
2
1
3
16
1
3
1
4
3
3
0
1
2
1
6
2
1
3
10
1
1
5
2
1
5
1
3
1
3
2
3
3
3
1
2
1
6
1
5
1
1
1
6
3
5
2
1
3
0
2
4
20
1
5
1
...

测试点 #4
Accepted
得分:100
用时:3 ms
内存:22076 KiB

输入文件

2000 2000
1 2
2 3
2 4
2 5
5 6
3 7
7 8
3 9
2 10
4 11
3 12
9 13
7 14
14 15
11 16
15 17
17 18
13 19
11 20
5 21
10 22
6 23
2...
期望输出
1551
668
1350
1334
7
1253
9
634
1
8
10
2
7
5
10
3
4
3
4
2
1
10
7
4
5
4
7
2
3
8
2
8
1
57
10
2
1
7
9
8
1
5
6
2
8
6
0
8
10
...
你的输出
1551
668
1350
1334
7
1253
9
634
1
8
10
2
7
5
10
3
4
3
4
2
1
10
7
4
5
4
7
2
3
8
2
8
1
57
10
2
1
7
9
8
1
5
6
2
8
6
0
8
10
...

测试点 #5
Accepted
得分:100
用时:3 ms
内存:22076 KiB

输入文件

2000 2000
1 2
1 3
2 4
2 5
5 6
4 7
1 8
4 9
2 10
5 11
2 12
12 13
10 14
11 15
12 16
6 17
11 18
18 19
1 20
12 21
4 22
16 23
...
期望输出
741
6
3
7
1033
45
988
9
7
932
6
1
5
15
1
7
1
7
4
2
4
1
3
3
7
4
12
1
6
1
5
1
7
1
11
7
2
6
1
7
1
6
10
1
0
8
1
6
9
4
6
5
16...
你的输出
741
6
3
7
1033
45
988
9
7
932
6
1
5
15
1
7
1
7
4
2
4
1
3
3
7
4
12
1
6
1
5
1
7
1
11
7
2
6
1
7
1
6
10
1
0
8
1
6
9
4
6
5
16...

测试点 #6
Accepted
得分:100
用时:104 ms
内存:22076 KiB

输入文件

100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 ...
期望输出
23156
53499
34233
14300
19077
48820
9846
12446
4837
87279
3251
83147
1398
42197
1146
24853
80057
25216
674
402
77
10588
...
你的输出
23156
53499
34233
14300
19077
48820
9846
12446
4837
87279
3251
83147
1398
42197
1146
24853
80057
25216
674
402
77
10588
...

测试点 #7
Accepted
得分:100
用时:92 ms
内存:22076 KiB

输入文件

100000 100000
1 2
1 3
3 4
3 5
4 6
3 7
2 8
3 9
3 10
8 11
10 12
11 13
1 14
6 15
10 16
15 17
3 18
15 19
13 20
10 21
3 22
17...
期望输出
65378
13
12
48800
75321
53016
4
10
12
12
3789
13
18
75073
64745
13
36012
7
8
18
32428
47674
14
15149
17
10
28362
72939
7...
你的输出
65378
13
12
48800
75321
53016
4
10
12
12
3789
13
18
75073
64745
13
36012
7
8
18
32428
47674
14
15149
17
10
28362
72939
7...

测试点 #8
Accepted
得分:100
用时:90 ms
内存:22076 KiB

输入文件

100000 100000
1 2
1 3
2 4
3 5
5 6
6 7
3 8
8 9
6 10
10 11
9 12
12 13
2 14
1 15
8 16
15 17
8 18
13 19
10 20
6 21
9 22
8 23...
期望输出
95180
54508
15761
3
10
35181
6
9
9
29475
63875
49672
50171
57093
16
1
9
12
9
8
7
3
562
15
1
9
11
10
12
5
18
3
11
1
8
1
9...
你的输出
95180
54508
15761
3
10
35181
6
9
9
29475
63875
49672
50171
57093
16
1
9
12
9
8
7
3
562
15
1
9
11
10
12
5
18
3
11
1
8
1
9...

测试点 #9
Accepted
得分:100
用时:92 ms
内存:22076 KiB

输入文件

100000 100000
1 2
2 3
2 4
4 5
4 6
6 7
5 8
6 9
7 10
3 11
1 12
8 13
7 14
8 15
7 16
6 17
1 18
13 19
5 20
15 21
19 22
6 23
1...
期望输出
8739
8
69238
12
32327
75695
21256
12
3
1
13
1
17
1
9
1
13
1
1
10
1
13
11
2
4
8
9
2
1
14
8
7
2
36
1
16
1
8
14
2
1
10
9
9
...
你的输出
8739
8
69238
12
32327
75695
21256
12
3
1
13
1
17
1
9
1
13
1
1
10
1
13
11
2
4
8
9
2
1
14
8
7
2
36
1
16
1
8
14
2
1
10
9
9
...

测试点 #10
Accepted
得分:100
用时:94 ms
内存:22076 KiB

输入文件

100000 100000
1 2
1 3
3 4
2 5
2 6
1 7
2 8
2 9
2 10
7 11
2 12
12 13
5 14
5 15
14 16
6 17
14 18
13 19
18 20
11 21
3 22
21 ...
期望输出
13074
12
12
14721
57069
12
8
9
1885
15781
11
11
16047
9
58692
7
11
40479
4
9
7
58013
15
12
8
20297
7
8
98652
10
5
6
11
6...
你的输出
13074
12
12
14721
57069
12
8
9
1885
15781
11
11
16047
9
58692
7
11
40479
4
9
7
58013
15
12
8
20297
7
8
98652
10
5
6
11
6...