OI - 树上竞技meeting(NOIP模拟赛) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 树上竞技meeting(NOIP模拟赛)

发表于 分类于 Valine：

这就是停课第一天吗

# 题面

点击展开/折叠 题面

给出一棵 $n$ 个点的树，在树上随机指定 $m$ 个特殊点 $\mathbb S=\{s_1,s_2,\dots,s_m\}$。然后对于这种特殊点的情况，选取一个点 $u$ 使得 $\sum dist(u,s_i)$ 最小，该最小值记为 $V(\mathbb S)$，形式化的：

$$V(\mathbb S)=\min_{u}\{\sum_{v\in \mathbb S}dist(u,v)\}$$

对于所有可能的 $\mathbb S$，求它们的 $V(\mathbb S)$ 之和。

$1\le m\le n\le10^6$

# 解析

对于路径和问题比较常见的做法是把每条路径的贡献分到一个点或一条边上，这道题路径的长度是与边有关的，比较容易想到计算一条边在所有 $\mathbb S$ 中被经过的总次数。

一条边 $(u,v)$ 会把树分成两块，假设两块中分别有 $x,m-x$ 个特殊点，且两块的点数分别为 $t,n-t$，组合数简单计算可得这样的 $\mathbb S$ 一共有 $\binom{t}{x}\binom{n-t}{m-x}$ 种。

然后就有一个比较容易懂的结论（但是我没有注意到）——由于最终所有特殊点要到一个点，而一条边把树分成两个连通块，那么一定是某一个连通块的特殊点要经过这条边到另一个连通块去，则贪心地想，一定是特殊点较少的连通块向另一个连通块移动。

则 $(u,v)$ 被经过的次数为 $\min\{x,m-x\}$。于是 $(u,v)$ 的总贡献可以写为：

这样直接计算可以做到 $O(nm)$ 的复杂度。

然而要继续优化，这个思路本身没有办法再优化，只能再对这个式子进行处理。首先想到的是先把 $\min$ 给去掉——令 $k=\lfloor\frac {m-1}2\rfloor$（暂时只考虑 $m$ 是奇数，$m$ 是偶数时对于 $x=\frac m2$ 单独计算即可）

出现了两个差不多的求和式，其中的变量只有 $t$，可以定义函数 $G(t)$：

则 $W(u,v)=G(t)+G(n-t)$。

关键是怎么快速计算 $G(t)$，不妨先对式子化简：

后面这个求和式乍一眼很像 $\binom{n-1}{m-1}$——在前 $t-1$ 个（前一部分）里面取 $x-1$ 个，在后 $n-t$ 个（后一部分）里取 $m-x$ 个——但是并不完全一样，因为 $x\in[1,k]$，实际上前 $t-1$ 个只能取 $0\sim k-1$ 个。

当 $t-1\le k-1$ 时，前 $t-1$ 个可以取到 $0\sim t-1$ 个，此时确实是 $\binom{n-1}{m-1}$；

当 $t>k$ 时，考虑组合意义递推求解：相当于把“前一部分”的边界往右扩展了一位。在 $G(t-1)$ 对应的情况中，有一类方案

  • 在前 $t-2$ 个中选了 $k-1$ 个；
  • 选择了第 $t-1$ 个（第 $t-1$ 个就是 $G(t)$ 相对于 $G(t-1)$ 对应的“前一部分”中多出来的一个）；

这一类方案在“前一部分”的边界右移一位时，“前一部分”中就选了 $t$ 个，不合法，需要删去。而这种情况的方案数：

  • 在前 $t-2$ 个中选 $k-1$ 个：$\binom{t-2}{k-1}$；
  • 选了第 $t-1$ 个则在“后一部分”中除了 $t-1$ 还选了 $m-k-1$ 个：$\binom{n-t}{m-k-1}$；

综上

于是可以递推 $O(m)$ 预处理 $G(t)$。最后 DFS 一遍求解即可。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6+10,MOD=(int)1e9+7;
#define ci const int &

inline int Add(ci a,ci b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(ci a,ci b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(ci a,ci b){return int(1ll*a*b%MOD);}
inline int Pow(ci a,ci b){return b? Mul(Pow(Mul(a,a),b>>1),(b&1)? a:1):1;}

struct GRAPH{
	int head[N],to[N<<1],nxt[N<<1],ncnt;
	void AddEdge(ci u,ci v){
		int p=++ncnt,q=++ncnt;
		to[p]=v,nxt[p]=head[u],head[u]=p;
		to[q]=u,nxt[q]=head[v],head[v]=q;
	}
	inline int operator [](ci u){return head[u];}
}Gr;

int n,m,K,ans;
int fac[N],ifac[N],G[N];

void Init(){
	fac[0]=1;for(int i=1;i<N;i++) fac[i]=Mul(fac[i-1],i);
	ifac[N-1]=Pow(fac[N-1],MOD-2);for(int i=N-2;i>=0;i--) ifac[i]=Mul(ifac[i+1],i+1);
}
inline int Read(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
inline int Comb(ci b,ci a){return a>b? 0:Mul(fac[b],Mul(ifac[a],ifac[b-a]));}
int DFS(ci u,ci fa){
	int siz=1;
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(v==fa) continue;
		siz+=DFS(v,u);
	}
	if(m&1) ans=Add(ans,Add(Mul(siz,G[siz]),Mul(n-siz,G[n-siz])));
	else{
		ans=Add(ans,Add(Mul(siz,G[siz]),Mul(n-siz,G[n-siz])));
		ans=Add(ans,Mul(m/2,Mul(Comb(siz,m/2),Comb(n-siz,m/2))));
	}
	return siz;
}
int main(){
	freopen("meeting.in","r",stdin);
	freopen("meeting.out","w",stdout);
	Init();
	Read(n),Read(m);
	for(int i=2,u;i<=n;i++) Gr.AddEdge(Read(u),i);
	K=(m-1)/2;
	if(K){
		for(int S=1;S<=K;S++)
			G[S]=Comb(n-1,m-1);
		for(int S=K+1;S<=n;S++)
			G[S]=Sub(G[S-1],Mul(Comb(S-2,K-1),Comb(n-S,m-K-1)));
	}
	DFS(1,0);
	printf("%d\n",ans);
	return 0;
}

THE END

Thanks for reading!

> Linked 云鸟-网易云