题意

分析

考场爆零做法

考虑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<<"\tuse "<<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\n",2 * ans % mod);

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

标解

首先说一下前排的L君的做法。

先算贡献乘以方案的乘积

点连通块的个数=断边的个数+1，所以乘积

边连通块的个数=点连通块的个数-大小为一的点连通块数，所以乘积

然后算期望

总情况数\(=2^{n-1}\)，由于答案要乘\(2^n\)，所以答案等于上面的乘积乘2。

再说一下后排的L君的直觉正确做法。

直接算点连通块的期望

点连通块的乘积

所以点连通块的期望可以化简。

综上

期望为

#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\n",ans);

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

最后说一下B君的精妙做法

考虑一条边对点连通块个数的贡献，不断+1，断掉+0.5，所以就有该式。