TopCoder SRM 561 Orienteering 树形dp

题意: 给定了一棵树，以及树上一些节点为关键点，求出随机选出$k$个关键点后遍历它们的最短路径的期望

遍历关键点相当于要遍历一棵树，考虑遍历一棵树的最优决策

假设我们确定了一个根$u$，递归考虑每棵子树的问题

发现除了最后留在的那个点对应的路径$(u,v)$以外，所有的边都要被遍历两次

即答案$\sum _{e\in E} 2\cdot w(e)-dis(u,v)$

所以改变根就会发现，答案就是总长*2-直径长度

设总点数为$n$，包含的总关键点数为$m$，要选出$k$个点

Part1 总长计算

考虑对于每一条边计算产生的树跨过它的概率

设这条边两边的关键点的个数分别为$a,b(a+b=m)$

显然，这条边被跨过的概率就是

$\begin{aligned} 1-\frac{C(a,k)} {C(m,k)}-\frac{C(b,k)} {C(m,k)}\end{aligned}$ (即减去所有选出的关键点都在两边的概率) 设$\begin{aligned} f(i)=\frac{C(i,k)} {C(m,k)}=\frac{i!(m-k)!} {m!(i-k)!}\end{aligned} $

因为这个题目要计算double，所以求阶乘的精度会比较有问题

考虑递推求出$f(i)$，则有

$f(i)=\left\{\begin{aligned}1 && i=m \\ \frac{f(i+1)(i+1-k)} {i+1} && i这样递推就能比好得保证精度，然后直接对于每条边计算即可，复杂度为$O(n)$

Part2 直径长度计算

直径似乎是一个很难在树形$\mathrm{dp}$中确定的东西，因此考虑直接先枚举直径的两个端点

定义一棵树的直径两端点为最小的二元组$(A,B)$满足

$\begin{aligned} A因为$k>1$，所以两端点一定不同，不妨设两个端点分别为$A,B(A<B)$

则一个点$C$可以出现在树上的充要条件是

$(dis(A,C)>dis(A,B) \or dis(A,C)=dis(A,B)\and C \ge B)$

$\and (dis(B,C)>dis(A,B) \or dis(B,C)=dis(A,B)\and C \ge A)$

数出所有可以出现在树上的点个数$i$，则$(A,B)$为直径的概率应为$\frac{C(i-2,k-2)} {C(m,k)}$

即强制选取了$(A,B)$两个点

依然考虑递推求出

$\begin{aligned} f(i)=\frac{C(i-2,k-2)} {C(m,k)}=\frac{(i-2)!k(k-1)(m-k)!} {m!(i-k)!}\end{aligned}$

类似地，得到其递推式为

$f(i)=\left\{\begin{aligned}\frac{k(k-1)} {m(m-1)} && i=m \\ \frac{f(i+1)(i+1-k)} {i-1} && i这一部分复杂度为$O(m^3)$

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;

typedef pair <int,int> Pii;
typedef long long ll;
typedef double db;
#define mp make_pair
#define pb push_back
#define reg register
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0;
	int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=51;

int n,m,k;
int id[N][N],mk[2510],sz[2510],p[310];
vector <int> G[2520];
db dp[2510],ans;
int dis[2500][2500];

void Dfs(int u,int f) {
	sz[u]=mk[u]>0;
	for(int v:G[u]) if(v!=f) {
		Dfs(v,u),sz[u]+=sz[v];
		ans+=1-dp[sz[v]]-dp[m-sz[v]];
	}
}
void Dfs_Getdis(int rt,int u,int f){
	for(int v:G[u]) if(v!=f) 
		dis[rt][v]=dis[rt][u]+1,Dfs_Getdis(rt,v,u);
}

int A,B;

int Check(int u){
	if(dis[A][u]>dis[A][B]) return 0;
	if(dis[A][u]==dis[A][B] && u<B) return 0;
	if(dis[B][u]>dis[A][B]) return 0;
	if(dis[B][u]==dis[A][B] && u<A) return 0;
	return 1;
}

class Orienteering {
	public:
		double expectedLength(vector <string> field, int K) {
			rep(i,1,n) G[i].clear(); memset(id,0,sizeof id),memset(mk,0,sizeof mk);
			n=m=0,k=K;
			rep(i,0,field.size()-1) rep(j,0,field[i].size()-1) if(field[i][j]!='#') {
				id[i][j]=++n;
				if(field[i][j]=='*') p[mk[n]=++m]=n;
			}
			rep(i,0,field.size()-1) rep(j,0,field[i].size()-1) if(id[i][j]) {
				if(i<iend && id[i+1][j]) G[id[i][j]].pb(id[i+1][j]),G[id[i+1][j]].pb(id[i][j]);
				if(j<jend && id[i][j+1]) G[id[i][j]].pb(id[i][j+1]),G[id[i][j+1]].pb(id[i][j]);
			}
			rep(i,0,m) dp[i]=0;
			dp[m]=1;
			drep(i,m-1,k) dp[i]=dp[i+1]/(i+1)*(i+1-k);
			ans=0,Dfs(1,0),ans*=2; // 期望总长
			// 下面求期望直径长度
			rep(i,1,n) if(mk[i]) Dfs_Getdis(i,i,dis[i][i]=0);
			
			dp[m]=1.0*k*(k-1)/m/(m-1);
			drep(i,m-1,k) dp[i]=dp[i+1]/(i-1)*(i+1-k);
			rep(i,1,m) rep(j,i+1,m) {
				int c=0; A=p[i],B=p[j];
				rep(k,1,m) c+=Check(p[k]);
				if(c>=k) ans-=dis[A][B]*dp[c];
			}
			return ans;
		}
};


$\begin{aligned} \frac{\begin{aligned} \sum_{i=0}^{min(k,sz[u]) } C(sz[u],i)\cdot C(m-sz[u],k-i)\end{aligned} } {C(m,k)}\end{aligned}$ $\begin{aligned} \frac{\begin{aligned} \sum_{i=0}^{min(k,sz[u]) } sz[u]!(m-sz[u])!k!(m-k)!\cdot \end{aligned} } {m!i!(sz[u]-i)!(k-i)!(m-sz[u]-k+i)!}\end{aligned}$ $\begin{aligned} 1-\frac{C(sz[u],k)} {C(m,k)}-\frac{C(m-sz[u],k)} {C(m,k)}\end{aligned}$

$\frac{C(i,k)} {C(m,k)}=\frac{i!(m-k)!} {m!(i-k)!}$

i从m for 到 k

f(i)=f(i+1)/i(k-i+1)

$\frac{C(i-2,k-2)} {C(m,k)}=\frac{(i-2)!k(k-1)(m-k)!} {m!(i-k)!}$

i=m时，$f(m)=\frac{k(k-1)} {m(m-1)}$