题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1086
这道题可以说是手把手教你树分块要怎样分
进行dfs，每访问到一个点就进栈，当发现某个子树的点加到一起大于等于B后，就把它们算进一个块，然后不断弹栈，直到遇到当前点（有点像tarjan）
这样可以保证dfs一遍之后所有的块内的点不超过2B，然后剩下的那些无论加到哪个块中都是合法的
|
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<bits/stdc++.h> #define maxn 1010 #define pb push_back using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,B; int belong[maxn],sz[maxn]; int cap[maxn],tot; vector<int>go[maxn]; stack<int>stk; void dfs(int now,int fa){ stk.push(now); for(int i=0; i<go[now].size(); i++){ int to=go[now][i]; if(to==fa)continue; dfs(to,now); if(sz[now]+sz[to]>=B){ sz[now]=0; cap[++tot]=now; while(stk.top()!=now){ belong[stk.top()]=tot; stk.pop(); } } else sz[now]+=sz[to]; } sz[now]++; } void paint(int now,int fa,int c){ if(belong[now])c=belong[now]; else belong[now]=c; for(int i=0; i<go[now].size(); i++){ int to=go[now][i]; if(to==fa)continue; paint(to,now,c); } } int main(){ n=rd(),B=rd(); if(n<B){ puts("0"); return 0; } for(int i=1; i<n; i++){ int x=rd(),y=rd(); go[x].pb(y); go[y].pb(x); } dfs(1,0); if(!tot)cap[++tot]=1; paint(1,0,tot); printf("%d\n",tot); for(int i=1; i<=n; i++)printf("%d ",belong[i]); puts(""); for(int i=1; i<=tot; i++)printf("%d ",cap[i]); puts(""); return 0; } |
