[codeforces1060F][DP]Shrinking Tree

翻译

你有一棵$n$个点的树，做$n?1$次如下操作
随机选择一条当前存在的边并把他的两个端点缩起来，新端点的编号在两个端点间等概率随机
问最后每个点成为最后一个点的概率
$n\le 50$

题解

吼啊
先放一下参考了这位爷爷的
自己很辣鸡的一点就是遇见这种$n$不小不大的就不会玩了…
首先当然可以想到，枚举需要计算的顶点
然后把他拉到根节点，开始考虑怎么计算
然后就被自己常犯的错误迷倒了…就是一直在想怎么记录图的状态…真的跟个sb没啥区别
我们先把他变成计数问题，先钦定每次删掉的是哪个边。然后我们考虑在这个删边过程下，某个点存活的概率，不妨称之为方案数
求出来之后最后除掉排列即可
删边的过程可以看作是父亲节点合并到儿子节点，并更改了某个节点的编号
故可以先写出一个状态$f[i][j]$表示当前的根节点合并到了$i$点，并且$i$点子树中还有$j$条边没有被删除且最后根节点活了下来的方案数
可以知道的一点是，子树之间是互不影响的。因为假设某个点下传到了他的某个孩子，他的其他孩子还是会挂在他上面，下一步同样可以下传到原先的另外一个孩子
那么先解决一个问题，如果我们知道了两个互不影响的子树状态$f[x][i]$与$f[y][j]$，如何将其合并
设$siz[i]$表示$i$点的子树大小
那么其实就是已经被删除了的和还没有被删除的边的互相合并，即为
$$f[x][i]?f[y][j]?C_{i+j}^i?C_{siz[i]+siz[j]?i?j?1}^{siz[i]?i?1}$$
注意连接这两棵子树的还有一条边，这可以解释后面系数问题
那么现在其实只用考虑一个点$x$与一个子树$y$的转移了
我们需要知道一个根节点来到$x$时，子树还有多少边，设其为$u$
那么当一个点来到$y$时，同样也还需要知道子树有多少边，设其为$v$
所以在根节点在$x?>y$的过程中，$y$子树删除了$k=u?v$条边，分类讨论
在来到$x$之前，$(x,y)$这条边已经被合并，故这条边可以在已知的被删除了的$siz[y]?i?1$条边的空隙中被删除，且并不需要考虑最终是哪个点被保存了下来，方案数为
$$(siz[y]?i)?f[y][i]$$
否则，这条边会在之后被合并
那么转移就有
$$0.5?f[y][i]$$
上面分别需要满足$i$相等或者$y$的$i$严格小于$x$的$i$
实现时使用了一个$lin$数组记录了以上转移
意义为当根节点下传到$x$时，子树$y$的边还有$i$条的合法方案
复杂度$O(n^3)$

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define double long double
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(int x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(int x){
    write(x);putchar('\n');}
const int MAXN=55;
struct edge{
    int x,y,next;}a[2*MAXN];int len,last[MAXN];
void ins(int x,int y){
    len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
double pre[MAXN];
double f[MAXN][MAXN],temp[MAXN],lin[MAXN];
int siz[MAXN];
double C(int n,int m){
    return pre[n]/(pre[m]*pre[n-m]);}
void dp(int x,int fa)
{
    f[x][0]=1;siz[x]=1;for(int k=last[x];k;k=a[k].next){
    int y=a[k].y;if(y!=fa){
    dp(y,x);for(int i=0;i<=siz[y];i++){
    lin[i]=0;for(int j=0;j<siz[y];j++){
    if(j<i)lin[i]+=f[y][j]*0.5;//到他的时候他跟他儿子这条边还没有被删 else lin[i]+=f[y][i];//否则他跟他儿子的边随时可以删掉 }}for(int i=0;i<=siz[x]+siz[y];i++)temp[i]=0;for(int i=0;i<siz[x];i++)for(int j=0;j<=siz[y];j++)temp[i+j]+=f[x][i]*lin[j]*C(i+j,i)*C(siz[x]+siz[y]-i-j-1,siz[x]-i-1);siz[x]+=siz[y];for(int i=0;i<=siz[x];i++)f[x][i]=temp[i];}}
}
int n;
int main()
{
    pre[0]=1;for(int i=1;i<=50;i++)pre[i]=pre[i-1]*i;n=read();for(int i=1;i<n;i++){
    int x=read(),y=read();ins(x,y);ins(y,x);}for(int i=1;i<=n;i++){
    dp(i,0);printf("%.10Lf\n",f[i][n-1]/pre[n-1]);}return 0;
}