AT4352 [ARC101C] Ribbons on Tree

解析

其实想到了断边按连通块容斥的做法。

但不知道为啥觉得没前途弃了…

悲。

考虑容斥，设 f[x][i] 表示 x 子树内与 x 所连的联通块有 i 个节点的方案数，第三维朴素是记录连通块个数，但其实只需要记一个 0/1 表示奇偶性即可。

然后题解奥妙重重的把这一步都取了：断奇数次贡献负，断偶数次贡献正，那直接每次断边的时候把 dp 值取反即可。

代码

#include<bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned long long#define debug(...) fprintf(stderr,__VA_ARGS__)#define ok debug("OK\n")using namespace std;const int N=5050;const int mod=1e9+7;inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;}inline ll ksm(ll x,ll k,int mod){ll res(1);while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res;}int n;ll f[N][N],tmp[2][N],top[N];vector<int>e[N];ll w[N];void dfs(int x,int fa){for(int to:e[x]){if(to==fa) continue;dfs(to,x); }memset(tmp,0,sizeof(tmp));int now=1,pre=0,mx=1;tmp[now][1]=1;for(int to:e[x]){if(to==fa) continue;swap(now,pre);memset(tmp[now],0,sizeof(tmp[now]));for(int i=0;i<=top[to];i++){for(int j=1;j<=mx;j++){(tmp[now][i+j]+=f[to][i]*tmp[pre][j])%=mod;}}mx+=top[to];}top[x]=mx;for(int i=1;i<=mx;i++){f[x][i]=tmp[now][i];(f[x][0]+=mod-tmp[now][i]*w[i]%mod)%=mod;}return;}signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();w[0]=1;for(int i=1;i<=n;i++) w[i]=(i&1)?0:w[i-2]*(i-1)%mod;for(int i=1;i<n;i++){int x=read(),y=read();e[x].push_back(y);e[y].push_back(x);}dfs(1,0);printf("%lld\n",mod-f[1][0]);return 0;}