题意

给出一棵无根树，求本质不同的独立集数模100000000710000000071000000007的值。

n≤500000n\le 500000n≤500000

题解

如果是有根树就好做多了。然而无根树可以找重心作为根，转化为有根树。

那么考虑有根树的本质不同的独立集数怎么求。

直接dpdpdp就行了。用f[i][0]f[i][0]f[i][0]表示iii不选的独立集数，f[i][1]f[i][1]f[i][1]表示iii要选的独立集数。

转移的时候要考虑本质是否不同。做法是树hashhashhash。把子节点的hashhashhash值排序后，值相同的子树拿出来一起考虑，用简单组合数计算。求组合数可以暴力求，总时间复杂度是O(n)O(n)O(n)的。

还有问题就是一颗无根树可能重心在边上，那么我们把这条边新建一个点作为根，同样dpdpdp就行了。求最终答案的时候要特别考虑一下。

时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)，因为要排序。

CODE

底数选的好hashhashhash可能随便过，否则就要多搞点信息进去，比如儿子个数什么的。。

#pragma GCC optimize (3)

#include <bits/stdc++.h>

using namespace std;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

void read(int &res){

	char ch; for(;!isdigit(ch=getc()););

	for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');

}

typedef long long LL;

typedef unsigned long long ULL;

const int MAXN = 500005;

const int mod = 1e9 + 7;

const ULL p = 998244353;

int n, fir[MAXN], to[MAXN<<1], nxt[MAXN<<1], cnt;

inline void link(int u, int v) { to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt; }

int rt[2];

int dfs(int u, int ff) {

	int re = 1, tmp; bool can = 1;

	for(int i = fir[u], v; i; i = nxt[i])

		if((v=to[i]) != ff) {

			re += (tmp = dfs(v, u));

			if(tmp<<1 > n) can = 0;

		}

	if(re<<1 < n) can = 0;

	if(can) rt[bool(rt[0])] = u;

	return re;

}

ULL hsh[MAXN];

int f[MAXN][2], c[MAXN], inv[MAXN];

inline bool cmp(int i, int j) { return hsh[i] < hsh[j]; }

inline int C(int N, int M) {

	int re = 1;

	while(M && re) re = 1ll * re * (N--) % mod * inv[M--] % mod;

	return re;

}

void dp(int u, int ff) {

	f[u][0] = f[u][1] = 1;

	hsh[u] = 233333;

	for(int i = fir[u], v; i; i = nxt[i])

		if((v=to[i]) != ff) dp(v, u);

	int cur = 0;

	for(int i = fir[u], v; i; i = nxt[i])

		if((v=to[i]) != ff) c[++cur] = v;

	sort(c + 1, c + cur + 1, cmp);

	for(int i = 1, j, v; i <= cur; i = j) {

		v = c[i];

		for(j = i; j <= cur && hsh[c[j]] == hsh[v]; ++j)

			hsh[u] = hsh[u] * p ^ hsh[c[j]];

		f[u][0] = 1ll * f[u][0] * C(((f[v][0]+f[v][1])%mod + j-i-1)%mod, j-i) % mod;

		f[u][1] = 1ll * f[u][1] * C((f[v][0] + j-i-1)%mod, j-i) % mod;

	}

	hsh[u] *= p * p;

	hsh[u] = (hsh[u] + (ULL)cur + 1ull) * p;

}

inline void pre(int N) {

	inv[0] = inv[1] = 1;

	for(int i = 2; i <= N; ++i) inv[i] = 1ll * (mod - mod/i) * inv[mod%i] % mod;

}

int main () {

	read(n); pre(n);

	for(int i = 1, u, v; i < n; ++i) read(u), read(v), link(u, v), link(v, u);

	dfs(1, 0);

	int r = rt[0];

	if(rt[1]) {

		r = ++n;

		for(int i = fir[rt[0]]; i; i = nxt[i]) if(to[i] == rt[1]) to[i] = r;

		for(int i = fir[rt[1]]; i; i = nxt[i]) if(to[i] == rt[0]) to[i] = r;

		link(r, rt[0]), link(r, rt[1]);

	}

	dp(r, 0);

	if(rt[1]) {

		int ans;

		if(hsh[rt[0]] != hsh[rt[1]]) ans = (1ll*f[rt[0]][0]*f[rt[1]][0]%mod + 1ll*f[rt[0]][0]*f[rt[1]][1]%mod + 1ll*f[rt[0]][1]*f[rt[1]][0]%mod) % mod;

		else ans = (C(f[rt[0]][0] + 1, 2) + 1ll*f[rt[0]][0]*f[rt[1]][1]%mod) % mod;

		printf("%d\n", ans);

	}

	else printf("%d\n", (f[r][0] + f[r][1]) % mod);

}

巴特西

BZOJ 3162 / Luogu P4895: 独钓寒江雪树hash+DP

题意

题解

CODE

最新文章

热门文章

巴特西

BZOJ 3162 / Luogu P4895: 独钓寒江雪 树hash+DP

题意

题解

CODE

最新文章

热门文章

BZOJ 3162 / Luogu P4895: 独钓寒江雪树hash+DP