【2020 Multi-University 4 I】Imperative Meeting 题解

题目大意

  有一棵 $n$ 个结点的树，现有 $m$ 个人位于不同的结点，那么要让他们在同一结点相遇的话会有一个最小总路程。而“$m$个人位于不同结点”共有 $\binom nm$ 种情况，求这 $\binom{n}{m}$ 种情况的最小总路程之和，模 $10^9+7$。

  $m \le n \le 10^6$
  多测，$T \le 1000$，$\sum n \le 2\times 10^6$
  2s

$$\\$$ $$\\$$ $$\\$$

题解

  考虑每条边的贡献，一条边有贡献当且仅当这条边两侧都有人，且贡献等于两侧人数的较小值。形式化地说，假设一条边连接了 $x$ 子树和 $y$ 子树，那么这条边的贡献为：

$$\sum_{i=1}^{m-1} \binom{size_x}{i} \binom{size_y}{m-i} \min(i,m-i)$$

  把 $\min$ 拆掉变成

$$\sum_{i=1}^{\lfloor \frac{m-1}{2} \rfloor} i\binom{size_x}{i} \binom{size_y}{m-i} + \sum_{i=1}^{\lfloor \frac{m-1}{2} \rfloor}i\binom{size_y}{i} \binom{size_x}{m-i} + [m为偶数]\frac m2 \binom{size_x}{\frac m2} \binom{size_y}{\frac m2}$$

  这式子共 3 项，最后一项对于每条边单独算一下就行了，所以要算前两项，以第一项为例做一个变形把乘 $i$ 去掉：

$$\begin{aligned} &\sum_{i=1}^{\lfloor \frac{m-1}{2} \rfloor} i\binom{size_x}{i} \binom{size_y}{m-i} \\ =& \sum_{i=1}^{\lfloor \frac{m-1}{2} \rfloor} i\cdot\frac{size_x!}{i!\cdot(size_x-i)!}\binom{size_y}{m-i} \\ =& \sum_{i=1}^{\lfloor \frac{m-1}{2} \rfloor} \frac{size_x \cdot (size_x-1)!}{(i-1)!\cdot(size_x-i)!}\binom{size_y}{m-i} \\ =& size_x\sum_{i=1}^{\lfloor \frac{m-1}{2} \rfloor} \binom{size_x-1}{i-1} \binom{size_y}{m-i} \end{aligned}$$

  注意到 $size_x+size_y=n$，记 $h_s=\sum_{i=1}^{\lfloor \frac{m-1}{2} \rfloor} \binom{s-1}{i-1} \binom{n-s}{m-i}$，结果发现这玩意是能递推的！
  有两种方法能够得到递推结果。
  一种是考虑 $h_s$ 的组合意义：把 $m-1$ 个球放到 $n-1$ 个盒子里，每个盒子最多放 $1$ 个球，且要求前 $s-1$ 个盒子最多只能有 $\lfloor \frac{m-1}{2} \rfloor-1$ 个球，问方案数。
  $m-1$ 个球放入 $n-1$ 个盒子共 $\binom{n-1}{m-1}$ 种方案，这也是 $h_1$ 的值。随着 $s$ 的增大，只会有越来越多的方案变得非法。从 $h_{s-1}$ 到 $h_s$ 变得非法的方案，即为前 $s-2$ 个盒子已经放够了 $\lfloor \frac{m-1}{2} \rfloor -1$ 个球，而第 $s-1$ 个盒子又放了一个球，其余球放在后面的盒子里，方案数为 $\binom{s-2}{\lfloor \frac{m-1}{2} \rfloor -1}\binom{n-s}{m-1-\lfloor \frac{m-1}{2} \rfloor}$。
  另一种方法是硬推：

$$h_{s+1}-h_s = \sum_{i=1}^{\lfloor \frac{m-1}{2} \rfloor} \binom{s}{i-1}\binom{n-s-1}{m-i}-\binom{s-1}{i-1}\binom{n-s}{m-i}$$

  把 $i=1$ 单独拉出来，其余的把 $\binom{s}{i-1}$ 拆成 $\binom{s-1}{i-1}+\binom{s-1}{i-2}$、把 $\binom{n-s}{m-i}$ 拆成 $\binom{n-s-1}{m-i}+\binom{n-s-1}{m-i-1}$，然后基本上所有的项都被消去了，能得到同样的结果。式子太长就不写了。

  于是，$O(n)$ 递推出 $h$，然后每条边单独算贡献，就得到答案了。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=1e6+5;
const LL mo=1e9+7;

int n,m,mh;
vector<int> e[maxn];

LL Pow(LL x,LL y)
{
	LL re=1;
	for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
	return re;
}

LL fac[maxn],inv[maxn];
void C_Pre(int n)
{
	fac[0]=1;
	fo(i,1,n) fac[i]=fac[i-1]*i%mo;
	inv[n]=Pow(fac[n],mo-2);
	fd(i,n-1,0) inv[i]=inv[i+1]*(i+1)%mo;
}
LL C(int n,int m) {return (n>=m && m>=0) ?fac[n]*inv[m]%mo*inv[n-m]%mo :0 ;}

void ReadInt(int &data)
{
	data=0;
	char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	do{
		data=(data<<3)+(data<<1)+ch-'0';
		ch=getchar();
	} while (ch>='0' && ch<='9');
}

LL h[maxn];
void Pre()
{
	int mhv=(m-1)>>1;
	if (mhv==0)
	{
		fo(i,1,n-1) h[i]=0;
		return;
	}
	h[1]=C(n-1,m-1);
	fo(i,2,n-1) h[i]=(h[i-1]-C(i-2,mhv-1)*C(n-i,m-1-mhv)%mo+mo)%mo;
	fo(i,1,n-1) (h[i]*=i)%=mo;
}

int size[maxn];
void dfs_size(int k,int last)
{
	size[k]=1;
	for(int son:e[k]) if (son!=last)
	{
		dfs_size(son,k);
		size[k]+=size[son];
	}
}

LL ans;
void dfs_ans(int k,int last)
{
	for(int son:e[k]) if (son!=last)
	{
		(ans+=h[size[son]]+h[n-size[son]]+((m&1) ?0 :C(size[son],mh)*C(n-size[son],mh)%mo*mh ))%=mo;
		dfs_ans(son,k);
	}
}

int T;
int main()
{
	C_Pre(1e6);
	
	scanf("%d",&T);
	while (T--)
	{
		ReadInt(n), ReadInt(m);
		mh=m>>1;
		fo(i,1,n) e[i].clear();
		fo(i,2,n)
		{
			int x;
			ReadInt(x);
			e[x].push_back(i);
		}
		
		Pre();
		dfs_size(1,0);
		ans=0;
		dfs_ans(1,0);
		
		printf("%lld\n",ans);
	}
}