题意
分析
考场爆零做法
考虑dp，用(f(i,j,0/1))表示i及其子树中形成j个边连通块的方案数，其中i是否向外连边。
(O(n^3))，转移方程太复杂就打挂了。
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#define rg register
#define il inline
#define co const
#pragma GCC optimize ("O0")
using namespace std;
template<class T> il T read(T&x)
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return x=data*w;
}
typedef long long ll;
const int INF=0x7fffffff;
const int MAXN=3e2+7,mod=1e9+7;
int n;
struct Edge
{
int nx,to;
}E[MAXN<<1];
int head[MAXN],ecnt;
void addedge(int x,int y)
{
E[++ecnt].to=y;
E[ecnt].nx=head[x],head[x]=ecnt;
}
ll f[MAXN][MAXN][2];
void dfs(int x,int fa)
{
// cerr<<"dfsing "<<x<<endl;
f[x][0][0]=1;
for(int i=head[x];i;i=E[i].nx)
{
int y=E[i].to;
if(y==fa)
continue;
dfs(y,x);
for(int j=(n>>1);j>0;--j)
{
// cerr<<" con "<<j<<endl;
ll t1=0,t2=0,t3=0; // edit 1
for(int k=0;k<=j;++k)
{
t1 += f[x][k][0] * f[y][j-k][0] % mod;
t1 += f[x][k][0] * f[y][j-k][1] % mod;
t3 += f[x][k][1] * f[y][j-k][0] % mod;
t3 += f[x][k][1] * f[y][j-k][1] % mod;
t1 %= mod,t3 %= mod;
if(j-k-1>=0)
t2 += f[x][k][0] * f[y][j-k-1][0] % mod;
t2 += f[x][k][1] * f[y][j-k][0] % mod;
t2 += f[x][k][0] * f[y][j-k][1] % mod;
t2 += f[x][k][1] * f[y][j-k+1][1] % mod;
t2 %= mod;
// cerr<<" use "<<k<<" t1="<<t1<<" t2="<<t2<<endl;
}
// cerr<<" t1="<<t1<<" t2="<<t2<<endl;
(f[x][j][0] += t1) %= mod;
(f[x][j][1] += t3 + t2) %= mod;
}
}
/* for(int j=0;j<=(n>>1);++j)
{
cerr<<"f["<<x<<"]["<<j<<"][0]="<<f[x][j][0]<<endl;
cerr<<"f["<<x<<"]["<<j<<"][1]="<<f[x][j][1]<<endl;
}*/
}
int main()
{
freopen("changchun.in","r",stdin);
freopen("changchun.out","w",stdout);
read(n);
for(int i=1;i<n;++i)
{
int x,y;
read(x);read(y);
addedge(x,y);
addedge(y,x);
}
dfs(1,0);
ll ans=0;
for(int i=1;i<=(n>>1);++i)
{
(ans += i * (f[1][i][0] + f[1][i][1]) % mod) %= mod;
}
printf("%lld
",2 * ans % mod);
// fclose(stdin);
// fclose(stdout);
return 0;
}
标解
首先说一下前排的L君的做法。
先算贡献乘以方案的乘积
点连通块的个数=断边的个数+1，所以乘积
[=sum_{i=0}^{n-1} (i+1) inom{n-1}{i}
]
边连通块的个数=点连通块的个数-大小为一的点连通块数，所以乘积
[=sum_{i=0}^{n-1} (i+1) inom{n-1}{i} - sum_{i=1}^{n}2^{n-1-deg_i}
]
然后算期望
总情况数(=2^{n-1})，由于答案要乘(2^n)，所以答案等于上面的乘积乘2。
再说一下后排的L君的直觉正确做法。
直接算点连通块的期望
点连通块的乘积
[sum_{i=0}^{n-1}(i+1) inom{n-1}{i} \
=sum_{i=0}^{n-1}frac{n+1}{2} inom{n-1}{i} \
=frac{n+1}{2} sum_{i=0}^{n-1} inom{n-1}{i} \
=frac{n+1}{2}2^{n-1} \
]
所以点连通块的期望可以化简。
综上
期望为
[(n+1)2^{n-1}-sum_{i=1}^{n}2^{n-deg_i}
]
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#define rg register
#define il inline
#define co const
#pragma GCC optimize ("O0")
using namespace std;
template<class T> il T read(T&x)
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return x=data*w;
}
typedef long long ll;
const int INF=0x7fffffff;
const int MAXN=1e6+8,mod=1e9+7;
int deg[MAXN];
int pow2[MAXN];
int main()
{
freopen("changchun.in","r",stdin);
freopen("changchun.out","w",stdout);
int n;
read(n);
pow2[0]=1;
for(int i=1;i<n;++i)
{
int x,y;
read(x);read(y);
++deg[x],++deg[y];
pow2[i] = pow2[i-1] << 1;
if(pow2[i] >= mod)
pow2[i] -= mod;
}
int ans = (ll)(n + 1) * pow2[n-1] % mod;
for(int i=1;i<=n;++i)
{
(ans += mod - pow2[n - deg[i]]) %= mod;
}
printf("%d
",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
最后说一下B君的精妙做法
考虑一条边对点连通块个数的贡献，不断+1，断掉+0.5，所以就有该式。