题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1086
来学习树上莫队的前置技能——树分块
题解让我们来%Po娘:《手把手教你块状树系列》
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1000+9; const int M = N * 2; int head[N],to[M],nxt[M],stk[M],top; int num[N],pri[N],n,lim,cnt; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void Add_Edge(int u, int v) { static int T = 0; to[++T] = v; nxt[T] = head[u]; head[u] = T; to[++T] = u; nxt[T] = head[v]; head[v] = T; } void DFS(int w, int f, int bot) { for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { DFS(to[i],w,top); if (top - bot >= lim) { pri[++cnt] = w; for (int i=top;i>bot;i--) { num[stk[i]] = cnt; } top = bot; } } } stk[++top] = w; } int main(){ n = read(); lim = read(); for (int i=1;i<n;i++) { Add_Edge(read(),read()); } DFS(1,1,0); while (top) { num[stk[top--]] = cnt; } printf("%d\n",cnt); for (int i=1;i<=n;i++) { printf("%d%c",num[i],i==n?'\n':' '); } for (int i=1;i<=cnt;i++) { printf("%d ",pri[i]); } return 0; }