独钓寒江雪

题目描述

给定一棵无根树，求其中本质不同的独立集的个数对 $10^9+7$ 取模的结果。

$n \leq 5\times 10^5$ 。

题解

若有根，明显 DP， $f_{u,0/1}$ 表点 $u$ 选否个数。无根，寻重心以为根，有二则添点向之连边。以哈希判同构，是以组合。

得 beginend 哈希法：

for (int i = 1; i <= tot; i++) (((hash[u] *= BASE) += tmp[i].first) ^= tmp[i].first) += tmp[i].first;

代码

const int N = 5e5 + 5, mod = 1e9 + 7;
const int BASE = 19260817;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	struct Edge {
		int to, nxt;
	} e[N << 1];
	int head[N], tot;
	void add_edge (int u, int v) { e[++tot] = (Edge) {v, head[u]}, head[u] = tot; }

	int qpow (int a, int b) {
		int ans = 1;
		for (; b; b >>= 1, a = 1ll * a * a % mod)
			if (b & 1) ans = 1ll * ans * a % mod;
		return ans;
	}

	int rt;
	int siz[N], mx[N];
	void get_root(int u, int fa) {
		siz[u] = 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (v == fa) continue;
			get_root(v, u);
			siz[u] += siz[v];
			mx[u] = max(mx[u], siz[v]);
		}
		mx[u] = max(mx[u], n - siz[u]);
		if (!rt || mx[u] < mx[rt]) rt = u;
	}
	int fac[N], inv[N], pw[N];
	int f[N], g[N];
	unsigned ll hash[N];
	int r1 = 0, r2 = 0;
	pair<unsigned ll, int> tmp[N];
	void dp(int u, int fa) {
		hash[u] = 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (v == fa || u == r1 && v == r2 || u == r2 && v == r1) continue;
			dp(e[i].to, u);
		}
		int tot = 0;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (v == fa || u == r1 && v == r2 || u == r2 && v == r1) continue;
			tmp[++tot] = make_pair(hash[e[i].to], e[i].to);
		}
		sort(tmp + 1, tmp + tot + 1);
		for (int i = 1; i <= tot; i++) (((hash[u] *= BASE) += tmp[i].first) ^= tmp[i].first) += tmp[i].first;
		f[u] = g[u] = 1;
		int l = 1;
		while (l <= tot) {
			int r = l;
			while (r < tot && tmp[r + 1].first == tmp[r].first) r++;
			int s = r - l + 1, c = inv[s], w = g[tmp[l].second] + s - 1;
			for (int i = 0; i < s; i++) c = 1ll * c * (w - i) % mod;
			f[u] = 1ll * f[u] * c % mod;
			c = inv[s];
			w = (g[tmp[l].second] + f[tmp[l].second] + s - 1) % mod;
			for (int i = 0; i < s; i++) c = 1ll * c * (w - i) % mod;
			g[u] = 1ll * g[u] * c % mod;
			l = r + 1;
		}
	}
	int main () {
		n = Read();
		pw[0] = fac[0] = inv[0] = 1;
		for (int i = 1; i <= n + 1; i++) 
			pw[i] = 1ll * pw[i - 1] * n % mod, fac[i] = 1ll * fac[i - 1] * i % mod;
		inv[n + 1] = qpow (fac[n + 1], mod - 2);
		for (int i = n; i; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
		for (int i = 1; i < n; i++) {
			int u = Read(), v = Read();
			add_edge(u, v), add_edge(v, u);
		}
		get_root(1, 0);
		for (int i = 1; i <= n; i++)
			if (mx[i] == mx[rt]) r2 = r1, r1 = i;
		if (r2) n++, add_edge(n, r1), add_edge(n, r2), rt = n;
		dp(rt, 0);
		if (!r2) printf("%d\n", ((f[rt] + g[rt]) % mod + mod) % mod);
		else if (hash[r1] != hash[r2]) {
			int ans = g[rt];
			(ans -= 1ll * f[r1] * f[r2] % mod) %= mod;
			printf("%d\n", (ans + mod) % mod);
		} else {
			int ans = g[rt];
			int s = 2, c = inv[s], w = f[r2] + s - 1;
			for (int i = 0; i < s; i++) c = 1ll * c * (w - i) % mod;
			(ans -= c) %= mod;
			printf("%d\n", (ans + mod) % mod);
		}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}