题目大意
给你一棵有 n n n个点的树， n n n为偶数，点和点之间两两配对，配对的点之间的边被覆盖，问有多少种配对方式使得每一条边都被覆盖
题解
先说说我的暴力做法。当我想到这个问题时，我没想到会被谴责。我只想到暴力。 d p dp dp做法，设 f u , j f_{u,j} fu,j表示 u u u还有子树 j j j个点需要与子树外的点相匹配。不难发现，除了根，只要每个点的子树内都有与外匹配的点，每边都会被覆盖，所以从儿子开始 v v v转移到 u u u忽略 f v , 0 f_{v,0} fv,0可以直接直接实现 f v , 0 = 0 f_{v,0}=0 fv,0=0，加入一棵子树时再枚举一下子树中有多少个点与前面的点匹配，组合数算一下方案就可以做到 O ( n 3 ) O(n^3) O(n3) 写成代码大概长这样
for(int j=0;j<=siz[u];j++)
for(int k=0;k<=siz[v];k++)
for(int w=0;w<=min(j,k);w++)
add(g[j+k-2*w],f[u][j]*C(j,w)%mod*fac[w]%mod*f[v][k]%mod*C(k,w)%mod);
其中 C ( j , w ) = ( j w ) , f a c [ w ] = ∏ i = 1 w i C(j,w)=\binom{j}{w},fac[w]=\prod_{i=1}^wi C(j,w)=(wj),fac[w]=∏i=1wi，特别的 f a c [ 0 ] = 1 fac[0]=1 fac[0]=1， g g g表示转移后的 f u f_u fu 然后就开始想偏了，改变一下枚举方式，把 w w w移到前面
for(int w=0;w<=min(siz[u],siz[v]);w++)
for(int j=w;j<=siz[u];j++)
for(int k=w;k<=siz[v];k++)
add(g[j+k-2*w],(f[u][j]*C(j,w)%mod*fac[w]%mod)*(f[v][k]%mod*C(k,w)%mod)%mod);
不难发现后面两重循环是个卷积，直接 m t t mtt mtt优化到 O ( n 2 log n ) O(n^2\log n) O(n2logn)，虽然 n ≤ 5 e 3 n\le5e3 n≤5e3，但只要有信仰，各种奇怪优化都加上就能卡过!!! 贴一下通过代码
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#define _fore(i, a) for (ll i = head[(a)]; i; i = edge[i].nxt)
#define LN putchar('\n')
#define _dbg(...) 1
#define dbg(x) 1
using namespace std;
using ll = long long;
using i128 = __int128_t;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;
void read(int &res)
{
res=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
struct img {
double x, y;
void f(double xx = 0, double yy = 0) {
x = xx, y = yy;
}
img operator+(const img &c) {
return (img) {
x + c.x, y + c.y};
}
img operator-(const img &c) {
return (img) {
x - c.x, y - c.y};
}
img operator*(const img &c) {
double tx = x * c.x - y * c.y;
double ty = x * c.y + y * c.x;
return (img) {
tx, ty};
}
img operator/(double c) {
return (img) {
x / c, y / c};
}
img conj() {
return (img) {
x, -y};
}
};
using Poly = std::vector<img>;
Poly w;
int get_lim(int sum) {
int lim = 1, k = 0;
while (lim < sum)
lim <<= 1, k++;
return lim;
}
const double PI = acos(-1.0);
void pre_w(int n) {
static int LIM = (w = {
(img){
1, 0}, (img){
1, 0}}, 2);
int lim = get_lim(n);
if (lim <= LIM)
return;
w.resize(lim);
for (int l = LIM; l < lim; l *= 2) {
img p; // w[j + l] = w_{2l} ^ j
p.f(cos(PI / l), sin(PI / l));
for (int i = 0; i < l; i += 2) {
w[(l + i)] = w[(l + i) / 2];
w[l + i + 1] = w[l + i] * p;
}
}
LIM = lim;
}
void fft(Poly &f) {
int deg = f.size();
pre_w(deg);
for (int l = deg >> 1; l; l >>= 1)
for (int i = 0; i < deg; i += (l << 1))
for (int j = 0; j < l; j++) {
img x = f[i + j] + f[i + j + l];
f[i + j + l] = w[j + l] * (f[i + j] - f[i + j + l]);
f[i + j] = x;
}
}
void ifft(Poly &f) {
int deg = f.size();
pre_w(deg);
for (int l = 1; l < deg; l <<= 1)
for (int i = 0; i < deg; i += (l << 1))
for (int j = 0; j < l; j++) {
img x = f[i + j], y = f[i + j + l] * w[j + l];
f[i + j] = x + y, f[i + j + l] = x - y;
}
for (int i = 0; i < deg; i++)
f[i] = f[i] / deg;
std::reverse(f.begin() + 1, f.end());
}
vector<ll> intmod_mul(const vector<int> &a, const vector<int> &b, int p) {
const ll LIM = 1 << 15;
int n = a.size(), m = b.size();
int lim = get_lim(n + m - 1);
Poly A1(lim), A2(lim), Q(lim);
for (int i = 0; i < n; i++) {
A1[i].f(a[i] / LIM, a[i] % LIM);
A2[i].f(a[i] / LIM, -a[i] % LIM);
}
for (int i = 0; i < m; i++) {
Q[i].f(b[i] / LIM, b[i] % LIM);
}
fft(A1), fft(A2), fft(Q);
for (int i = 0; i < lim; i++)
A1[i] = A1[i] * Q[i];
for (int i = 0; i < lim; i++)
A2[i] = A2[i] * Q[i];
ifft(A1);
ifft(A2);
vector<ll> ans(n + m - 1);
for (int i = 0; i < m + n - 1; i++) {
ll a1b1 = ll((A1[i].x + A2[i].x + 1) / 2) % p;
ll a1b2 = ll((A1[i].y + A2[i].y + 1) / 2) % p;
ll a2b1 = ll((A1[i].y - A2[i].y + 1) / 2) % p;
ll a2b2 = ll((A2[i].x - A1[i].x + 1) / 2) % p;
ans[i] = (a1b1 * LIM + a1b2 + a2b1) * LIM + a2b2;
}
return ans;
}
const int N=5e3+100;
const ll mod=1e9+7;
ll ksm(ll a,ll b)
{
if(b==0) return 1;
ll tmp=ksm(a,b>>1);
if(b&1) return tmp*tmp%mod*a%mod;
else return tmp*tmp%mod;
}
int n,st[N+10],tot,siz[N+10];
struct edge
{
int to,last;
}e[N<<1|1];
void add(int a,int b)
{
e[++tot].to=b;
e[tot].last=st[a];
st[a]=tot;
}
ll fac[N+10],inv[N+10],f[N+10][N+10],g[N+10];
void init()
{
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod,inv[i]=ksm(fac[i],mod-2);
}
ll C(int n,int m){
return fac[n]*inv[m]%mod*inv[n-m]%mod;}
void add(ll &a,int b){
a+=b;if(a>=mod) a-=mod;}
int son[N+10];
void findson(int u,int fa)
{
siz[u]=1;
for(int i=st[u],v;i!=0;i=e[i].last)
{
v=e[i].to;
if(v==fa) continue;
findson(v,u),siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
const int B=20000;
void dfs(int u,int fa)
{
siz[u]=1,f[u][1]=1;
if(!son[u]) return;
int v=son[u];
dfs(v,u);
for(int j=0;j<=siz[u]+siz[v];j++) g[j]=0;
for(int w=0;w<=min(siz[u],siz[v]);w++)
{
if((siz[u]-w+1)*(siz[v]-w+1)>B)
{
int n=siz[u]-w+1,m=siz[v]-w+1,p=(int)mod;
dbg(n+m-1);
vector<int> a(n), b(m);
for (int j = 0; j < n; j++) a[j]=f[u][j+w]*C(j+w,w)%mod*fac[w]%mod;
for (int j = 0; j < m; j++) b[j]=f[v][j+w]*C(j+w,w)%mod;
auto ans = intmod_mul(a, b, p);
for(int j=2*w;j<=siz[u]+siz[v];j++) add(g[j-2*w],int(ans[j-2*w]%p));
}
else
for(int j=w;j<=siz[u];j++)
for(int k=w;k<=siz[v];k++)
add(g[j+k-2*w],f[u][j]*f[v][k]%mod*C(j,w)%mod*C(k,w)%mod*fac[w]%mod);
}
for(int j=0;j<=siz[u]+siz[v];j++) f[u][j]=g[j];
siz[u]+=siz[v];
for(int i=st[u];i!=0;i=e[i].last)
{
v=e[i].to;
if(v==fa||v==son[u]) continue;
dfs(v,u);
for(int j=0;j<=siz[u]+siz[v];j++) g[j]=0;
for(int w=0;w<=min(siz[u],siz[v]);w++)
{
if((siz[u]-w+1)*(siz[v]-w+1)>B)
{
int n=siz[u]-w+1,m=siz[v]-w+1,p=(int)mod;
dbg(n+m-1);
vector<int> a(n), b(m);
for (int j = 0; j < n; j++) a[j]=f[u][j+w]*C(j+w,w)%mod*fac[w]%mod;
for (int j = 0; j < m; j++) b[j]=f[v][j+w]*C(j+w,w)%mod;
auto ans = intmod_mul(a, b, p);
for(int j=2*w;j<=siz[u]+siz[v];j++) add(g[j-2*w],int(ans[j-2*w]%p));
}
else
for(int j=w;j<=siz[u];j++)
for(int k=w;k<=siz[v];k++)
add(g[j+k-2*w],f[u][j]*f[v][k]%mod*C(j,w)%mod*C(k,w)%mod*fac[w]%mod);
}
for(int j=0;j<=siz[u]+siz[v];j++) f[u][j]=g[j];
siz[u]+=siz[v];
}
if(u!=1) f[u][0]=0;
}
int main()
{
read(n),init();
for(int i=1,a,b;i<n;i++) read(a),read(b),add(a,b),add(b,a);
findson(1,0),dfs(1,0);
printf("%lld\n",f[1][0]);
return 0;
}
下面讲点正常的东西，考虑容斥，求出至少 k k k条边不能被覆盖的方案数，最后乘上容斥系数加起来就可以求出答案了， k k k条边将会把树分割成 k + 1 k+1 k+1个块，这些块中随意配对的方案数乘起来就行了，设 g i g_i gi表示 2 i 2i 2i个点随意配对的方案数，可以得到递推式 g i = g i − 1 + 2 g i − 2 ( 2 ( i − 1 ) 2 ) g_i=g_{i-1}+2g_{i-2}\binom{2(i-1)}{2} gi=gi−1+2gi−2(22(i−1))，大概思想就是考虑新加入的两个点自己配对还是与前面的点配对 然后还是考虑 d p dp dp解决这个问题，设 f u , i f_{u,i} fu,i表示 u u u子树内有 i i i个点没有配对，算上容斥系数之后的方案数，除根以外，在 i = 0 i=0 i=0时，这个点到它父亲的边一定是没有覆盖的，要乘上一个容斥系数 − 1 -1 −1
c o d e code code
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
void read(int &res)
{
res=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=5e3+100;
const ll mod=1e9+7;
ll ksm(ll a,ll b)
{
if(b==0) return 1;
ll tmp=ksm(a,b>>1);
if(b&1) return tmp*tmp%mod*a%mod;
else return tmp*tmp%mod;
}
int n,st[N+10],tot,siz[N+10];
struct edge
{
int to,last;
}e[N<<1|1];
void add(int a,int b)
{
e[++tot].to=b;
e[tot].last=st[a];
st[a]=tot;
}
ll fac[N+10],inv[N+10],f[N+10][N+10],tmp[N+10],g[N+10];
ll C(int n,int m){
return fac[n]*inv[m]%mod*inv[n-m]%mod;}
void init()
{
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod,inv[i]=ksm(fac[i],mod-2);
g[0]=g[1]=1;
for(int i=2;i<=(n>>1);i++) g[i]=(g[i-1]+g[i-2]*C(2*(i-1),2)%mod*2%mod)%mod;
}
void add(ll &a,int b){
a+=b;if(a>=mod) a-=mod;}
void dfs(int u,int fa)
{
siz[u]=1,f[u][1]=1;
for(int i=st[u],v;i!=0;i=e[i].last)
{
v=e[i].to;
if(v==fa) continue;
dfs(v,u);
for(int j=0;j<=siz[u]+siz[v];j++) tmp[j]=0;
for(int j=0;j<=siz[u];j++)
for(int k=0;k<=siz[v];k++)
add(tmp[j+k],f[u][j]*f[v][k]%mod);
for(int j=0;j<=siz[u]+siz[v];j++) f[u][j]=tmp[j];
siz[u]+=siz[v];
}
for(int i=2;i<=siz[u];i+=2) add(f[u][0],f[u][i]*g[i>>1]%mod);
f[u][0]=(mod-f[u][0])%mod;
}
int main()
{
read(n),init();
for(int i=1,a,b;i<n;i++) read(a),read(b),add(a,b),add(b,a);
dfs(1,0);
printf("%lld\n",(mod-f[1][0])%mod);
return 0;
}