(题目链接)
题意
求将树分为几个联通块,每个联通块大小大于B小于3B,是否可行。
Solution
题都没看就翻了题解。。
代码
// bzoj3757#include#include #include #include #include #include #define MOD 1000000007#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;inline LL getint() { LL x=0,f=1;char ch=getchar(); while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f;}const int maxn=1010;struct edge {int next,to;}e[maxn<<2];int head[maxn],size[maxn],pos[maxn],q[maxn],n,B,cnt,top,c,cap[maxn];void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt; e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;}void dfs(int x,int fa) { q[++top]=x; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) { dfs(e[i].to,x); if (size[x]+size[e[i].to]>=B) { size[x]=0; cap[++cnt]=x; while (q[top]!=x) pos[q[top--]]=cnt; } else size[x]+=size[e[i].to]; } size[x]++;}void paint(int x,int fa,int c) { if (pos[x]) c=pos[x]; else pos[x]=c; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) paint(e[i].to,x,c);}int main() { scanf("%d%d",&n,&B); for (int i=1;i