AtCoder Regular Contest 101 E - Ribbons on Tree(容斥+树形依赖背包)

Author Avatar
Sakits 9月 02, 2018

题解

  比赛的时候想到了容斥,但是树形依赖背包的子树版本确实没怎么写过…这题是不能dfs序的,dfs序背包无法维护子树信息所以做不了…强行思维定势了一波
  首先考虑断掉某条边后左右两个联通块的任意配对方案就是:

(n1)×(n3)×(n5)×...×3×1(n-1)\times(n-3)\times(n-5)\times...\times 3\times 1

  奇数显然为00
  接下来就是求出各个连通块个数的匹配方案数,容斥即可。
  求这个显然用背包DP就好了,边背包边容斥比较好写而且会小44倍常数…
  如果不边背包边容斥那么设fi,j,0/1f_{i,j,0/1}表示ii子树里,与ii在一个连通块里有jj个点,已有连通块数的奇偶性为0/10/1的方案。转移需要枚举两个奇偶性所以有44倍常数,而且转移挺麻烦的。
  边背包边容斥可以设fi,jf_{i,j}为表示ii子树里,与ii在一个连通块里有jj个点的方案,每次新增连通块转移的时候加个负号就好了。
  树形依赖背包如果写这种先DP后加size的话因为是刷表法,所以可能会对用于转移的DP数组修改到,得开个tmp数组用于存转移后的值。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
#define MOD(x) ((x)>=mod?(x)-mod:(x))
using namespace std;
const int maxn=5010, inf=1e9, mod=1e9+7;
struct edge{int too, pre;}e[maxn<<1];
int n, tot, x, y;
int last[maxn], size[maxn], f[maxn][maxn], g[maxn], tmp[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline void add(int x, int y){e[++tot]=(edge){y, last[x]}; last[x]=tot;}

void dfs(int x, int fa)
{
	size[x]=1; f[x][1]=1;
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa)
	{
		dfs(too, x);
		for(int j=1;j<=size[x]+size[too];j++) tmp[j]=0;
		for(int j=1;j<=size[x];j++)
		{
			for(int k=0;k<=size[too];k++)
			tmp[j+k]=(tmp[j+k]+1ll*f[x][j]*f[too][k])%mod;
		}
		for(int j=1;j<=size[x]+size[too];j++) f[x][j]=tmp[j];
		size[x]+=size[too];
	}
	for(int j=2;j<=size[x];j+=2)
	f[x][0]-=1ll*f[x][j]*g[j]%mod, f[x][0]=MOD(f[x][0]+mod);
}

int main()
{
	read(n);
	for(int i=1;i<n;i++) read(x), read(y), add(x, y), add(y, x);
	g[0]=1; for(int i=2;i<=n;i+=2) g[i]=1ll*g[i-2]*(i-1)%mod;
	dfs(1, 0);
	printf("%d\n", mod-f[1][0]);
}