uoj387题解

Posted on | Edited on | Comments:

学到了一个新的技巧，树形的依赖关系，把顺序翻转，就可以在依赖父亲和依赖子树之间相互转化.

每次选取最深的能选取的叶子，证明的话，画个图用一下调整法应该能证.

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define ele int
#define fi first
#define se second
using namespace std;
#define maxn 100010
ele n,m,ans,f[maxn],dep[maxn],deg[maxn];
vector<ele> res[maxn];
priority_queue<pair<ele,ele> > Q;
queue<ele> Q1;
int main(){
	scanf("%d%d",&n,&m);
	dep[0]=0;
	memset(deg,0,sizeof(deg));
	for (int i=1; i<n; ++i){
		scanf("%d",f+i);
		--f[i]; ++deg[f[i]];
		dep[i]=dep[f[i]]+1;
	}
	for (int i=0; i<n; ++i)
		if (!deg[i]) Q.push(make_pair(dep[i],i));
	ans=0;
	for (int i=0; i<n; ++i){
		if (Q.empty()){
			++ans;
			while (!Q1.empty()){
				ele k=Q1.front(); Q1.pop();
				Q.push(make_pair(dep[k],k));
			}
		}
		pair<ele,ele> k1=Q.top(); Q.pop();
		ele k=k1.se;
		if (res[ans].size()==m){
			++ans;
			while (!Q1.empty()){
				ele k=Q1.front(); Q1.pop();
				Q.push(make_pair(dep[k],k));
			}
		}
		res[ans].push_back(k);
		--deg[f[k]];
		if (!deg[f[k]]) Q1.push(f[k]);
	}
	printf("%d\n",ans+1);
	for (int i=ans; ~i; --i){
		printf("%d ",res[i].size());
		for (int j=res[i].size()-1; ~j; --j) printf("%d ",res[i][j]+1);
		puts("");
	}
	return 0;
}