CERC 17 J - Justified Jungle

传送门

题意

时限6s, 给你一颗\(n \leq 1e6\)的树，输出所有的\(i\)， 使得该树可以删除某\(i\)条边,使得删除后所有的连通块大小相等

题解

虽然有结论,但还是讲讲我的做法把, 或许有所启发
考虑将枚举删除边数转换为枚举连通块大小, 不妨设每个连通块大小为\(k\)

每次从树上删除一个大小恰为\(k\)的子树,如果这样可以删除整棵树,那么就可以,否则不行,正确性应该比较正确?

如何实现呢? 如果我们能够在较小的复杂度实现发现并删除一颗大小为\(k\)的子树,那么总复杂度就是调和级数级别的

考虑这样做: 我们预处理子树大小, 把每一个点按子树大小丢入一个桶中, 对于每一个\(k\), 我们从小到大扫描它的倍数, 用线段树加dfs序维护删除后的子树大小, 一开始把所有\(k\)大小的子树删除了,然后对于所有\(2k\)桶中的子树,他们当前的大小如果是\(k\)就删除,如果不是\(k\)就无解。

总复杂度\(O(nlog^2n)\)

实现

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define ls(x) (x*2)
#define rs(x) (x*2+1) 
#define ll long long 
using namespace std;

int read(){
	int num=0, flag=1; char c=getchar();
	while(!isdigit(c) && c!='-') c=getchar();
	if(c == '-') flag=-1, c=getchar();
	while(isdigit(c)) num=num*10+c-'0', c=getchar();
	return num*flag;
}

const int N = 1e6+10000;
int n;
vector<int> p[N];
int fa[N], dis[N], son[N], dfn[N], efn[N], cnt=0;

void dfs(int x){
	son[x] = 1;
	dfn[x] = ++cnt;
	for(auto nex : p[x]){
		if(nex == fa[x]) continue;
		fa[nex] = x;
		dis[nex] = dis[x] + 1;
		dfs(nex);
		son[x] += son[nex];
	}
	efn[x] = cnt;
}

struct Tree{
	int tree[N<<2];
	
	void push_up(int o){
		tree[o] = tree[ls(o)] + tree[rs(o)];
	}
	
	void build(int o, int l, int r){
		if(l == r){
			tree[o] = 1;
			return ;
		}
		
		int mid =(l+r)/2;
		if(tree[ls(o)] != (mid-l+1)) build(ls(o), l, mid);
		if(tree[rs(o)] != (r-mid)) build(rs(o), mid+1, r);
		push_up(o);
	}
	
	int query(int o, int l, int r, int ql, int qr){
		if(ql<=l && r<=qr) return tree[o];
		int mid=(l+r)/2, res=0;
		
		if(ql<=mid) res+=query(ls(o),l,mid, ql,qr);
		if(qr>mid) res+=query(rs(o), mid+1, r, ql,qr); 
		return res;
	} 
	
	void update(int o, int l, int r, int x, int v){
		if(l == r){
			tree[o] += v;
			return ;
		}
		
		int mid = (l+r)/2;
		if(x <= mid) update(ls(o),l,mid, x,v);
		else update(rs(o),mid+1,r, x,v);
		push_up(o);
	}
}t;
vector<int> s[N];


int check(int k){
	t.build(1,1,n);
	for(int i=1; i*k<=n; i++){
		for(auto x : s[i*k]){
			if(t.query(1,1,n,dfn[x],efn[x]) != k) return 0;
			t.update(1,1,n,dfn[x],-k);
		}
	}
	return 1;
}



int main(){
	n = read();
	for(int i=1; i<=n-1; i++){
		int u=read(), v=read();
		p[u].push_back(v);
		p[v].push_back(u);
	}
	
	dis[1] = 1;
	dfs(1);
	
	for(int i=1; i<=n; i++){
		s[son[i]].push_back(i);
	}
	
	for(int i=n-1; i>=1; i--){
		if(n % i) continue;
		if(check(i)){
			printf("%d ", n/i-1);
		}
	} 
	return 0;
}