TopCoder SRM 561 Orienteering(树形dp)
题意: 给定了一棵树，以及树上一些节点为关键点，求出随机选出(k)个关键点后遍历它们的最短路径的期望
遍历关键点相当于要遍历一棵树，考虑遍历一棵树的最优决策
假设我们确定了一个根(u)，递归考虑每棵子树的问题
发现除了最后留在的那个点对应的路径((u,v))以外，所有的边都要被遍历两次
即答案(sum _{ein E} 2cdot w(e)-dis(u,v))
所以改变根就会发现，答案就是总长*2-直径长度
设总点数为(n)，包含的总关键点数为(m)，要选出(k)个点
Part1 总长计算
考虑对于每一条边计算产生的树跨过它的概率
设这条边两边的关键点的个数分别为(a,b(a+b=m))
显然，这条边被跨过的概率就是
(egin{aligned} 1-frac{C(a,k)}{C(m,k)}-frac{C(b,k)}{C(m,k)}end{aligned}) (即减去所有选出的关键点都在两边的概率)
设$egin{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{egin{aligned}1 && i=m \ frac{f(i+1)(i+1-k)}{i+1} && i<mend{aligned} ight.)
这样递推就能比好得保证精度，然后直接对于每条边计算即可，复杂度为(O(n))
Part2 直径长度计算
直径似乎是一个很难在树形(mathrm{dp})中确定的东西，因此考虑直接先枚举直径的两个端点
定义一棵树的直径两端点为最小的二元组((A,B))满足
$egin{aligned} A<B，dis(A,B)=max_{u,vin V}{dis(u,v)}end{aligned} $
因为(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))两个点
依然考虑递推求出
(egin{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{egin{aligned}frac{k(k-1)}{m(m-1)} && i=m \ frac{f(i+1)(i+1-k)}{i-1} && i<mend{aligned} ight.)
这一部分复杂度为(O(m^3))
#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;
}
};
(egin{aligned} frac{egin{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})
(egin{aligned} frac{egin{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})
(egin{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)})