题意: 给定一棵 n 个点的树, 问删去某个点之后所有的树同构, 这样分割出来的树最多能有几棵
n<=4000
思路: 分割成至少两个 size 相等的联通块之后 size 必定小于 n/2, 与树的重心的定义相同
预处理出重心 (0,1 或 2 个) 之后上无根树同构板子
- #include <bits / stdc++.h> using namespace std;
- typedef long long ll;
- typedef unsigned int uint;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef pair <int,
- int> PII;
- typedef pair <ll,
- ll> Pll;
- typedef vector <int> VI;
- typedef vector <PII> VII;
- typedef pair <ll,
- ll> P;#define N 200010#define M 1000000#define INF 1e9#define fi first#define se second#define MP make_pair#define pb push_back#define pi acos( - 1)#define mem(a, b) memset(a, b, sizeof(a))#define rep(i, a, b) for (int i = (int) a; i <= (int) b; i++)#define per(i, a, b) for (int i = (int) a; i>= (int) b; i--)#define lowbit(x) x & ( - x)#define Rand(rand() * (1 <<16) + rand())#define id(x)((x) <= B ? (x) : m - n / (x) + 1)#define ls p << 1#define rs p << 1 | 1#define fors(i) for (auto i: e[x]) if (i != p)
- const int MOD = 1e9 + 7,
- inv2 = (MOD + 1) / 2;
- double eps = 1e-6;
- int dx[4] = { - 1,
- 1,
- 0,
- 0
- };
- int dy[4] = {
- 0,
- 0,
- -1,
- 1
- };
- int head[N],
- vet[N],
- nxt[N],
- sz[N],
- mx[N],
- d[N],
- tot,
- Size,
- root;
- int read() {
- int v = 0,
- f = 1;
- char c = getchar();
- while (c < 48 || 57 < c) {
- if (c == '-') f = -1;
- c = getchar();
- }
- while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48,
- c = getchar();
- return v * f;
- }
- ll readll() {
- ll v = 0,
- f = 1;
- char c = getchar();
- while (c < 48 || 57 < c) {
- if (c == '-') f = -1;
- c = getchar();
- }
- while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48,
- c = getchar();
- return v * f;
- }
- void add(int a, int b) {
- nxt[++tot] = head[a];
- vet[tot] = b;
- head[a] = tot;
- }
- void dfs1(int u, int fa) {
- int e = head[u];
- sz[u] = 1,
- mx[u] = 0;
- while (e) {
- int v = vet[e];
- if (v != fa) {
- dfs1(v, u);
- sz[u] += sz[v];
- mx[u] = max(mx[u], sz[v]);
- }
- e = nxt[e];
- }
- }
- int ra[N];
- int pw(int x, int y) {
- int res = 1;
- while (y) {
- if (y & 1) res = 1ll * res * x % MOD;
- x = 1ll * x * x % MOD;
- y>>= 1;
- }
- return res;
- }
- int inv(int x) {
- return pw(x, MOD - 2);
- }
- struct Sub {
- VI S;
- int d1,
- d2,
- H1,
- H2;
- Sub() {
- d1 = d2 = 0;
- S.clear();
- }
- void add(int d, int v) {
- S.pb(v);
- if (d> d1) d2 = d1,
- d1 = d;
- else if (d> d2) d2 = d;
- }
- int Hash() {
- H1 = H2 = 1;
- for (int i: S) {
- H1 = 1ll * H1 * (ra[d1] + i) % MOD;
- H2 = 1ll * H2 * (ra[d2] + i) % MOD;
- }
- return H1;
- }
- PII del(int d, int v) {
- if (d == d1) return {
- d2 + 1,
- 1ll * H2 * inv(ra[d2] + v) % MOD
- };
- return {
- d1 + 1,
- 1ll * H1 * inv(ra[d1] + v) % MOD
- };
- }
- };
- PII U[N];
- int n,
- i,
- x,
- y,
- A[N];
- Sub T[N];
- void prepare(int n) {
- rep(i, 0, n) ra[i] = rand() % MOD;
- }
- void dfsD(int u, int p) {
- Size++;
- T[u] = Sub();
- int e = head[u];
- while (e) {
- int v = vet[e];
- if (v != p) {
- dfsD(v, u);
- T[u].add(T[v].d1 + 1, T[v].H1);
- }
- e = nxt[e];
- }
- T[u].Hash();
- }
- void dfsU(int u, int p) {
- if (p != root) T[u].add(U[u].fi, U[u].se);
- A[u] = T[u].Hash();
- int e = head[u];
- while (e) {
- int v = vet[e];
- if (v != p) {
- U[v] = T[u].del(T[v].d1 + 1, T[v].H1);
- dfsU(v, u);
- }
- e = nxt[e];
- }
- }
- int isok(int root, int block) {
- int t[5000],
- c[5000];
- int s = 0;
- int e = head[root];
- while (e) {
- int v = vet[e];
- rep(i, 1, n) A[i] = 0;
- Size = 0;
- dfsD(v, root);
- dfsU(v, root);
- if (Size != block) return 0;
- s++;
- if (s == 1) {
- sort(A + 1, A + n + 1);
- rep(i, 1, n) c[i] = A[i];
- } else {
- sort(A + 1, A + n + 1);
- rep(i, 1, n) if (A[i] != c[i]) return 0;
- }
- e = nxt[e];
- }
- return 1;
- }
- int main() {
- VI r;
- srand(23333);
- prepare(5000);
- n = read();
- rep(i, 1, n) head[i] = d[i] = 0;
- tot = 0;
- rep(i, 1, n - 1) {
- int x = read(),
- y = read();
- add(x, y);
- add(y, x);
- d[x]++;
- d[y]++;
- }
- dfs1(1, 0);
- r.clear();
- rep(i, 1, n) if (d[i]>= 2 && max(mx[i], n - sz[i]) <= n / 2) r.pb(i);
- int ans = 0;
- for (int i = 0; i < r.size(); i++) {
- root = r[i];
- if (isok(r[i], mx[r[i]])) ans = max(ans, d[r[i]]);
- }
- if (ans == 0) printf("-1\n");
- else printf("%d\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3274309.html