当前位置: 代码迷 >> 综合 >> [codeforces1060F][DP]Shrinking Tree
  详细解决方案

[codeforces1060F][DP]Shrinking Tree

热度:48   发布时间:2023-12-19 04:33:55.0

翻译

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

题解

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

#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;
}
  相关解决方案