wordpress增加产品模块,魔方优化大师官网,微信推广平台怎么找,tp5做企业网站解析
神题。
把每个节点提到根 rt 单独考虑。 设 dpi,jdp_{i,j}dpi,j 表示当 rt 进入 i 时子树内还有 j 条边未合并的方案的期望之和#xff0c;gi,jg_{i,j}gi,j 表示当 rt 进入 i 的父亲时 i 的子树内#xff08;包括连向父亲的边#xff09;还有 j 条边未合并的方案…解析
神题。
把每个节点提到根 rt 单独考虑。 设 dpi,jdp_{i,j}dpi,j 表示当 rt 进入 i 时子树内还有 j 条边未合并的方案的期望之和gi,jg_{i,j}gi,j 表示当 rt 进入 i 的父亲时 i 的子树内包括连向父亲的边还有 j 条边未合并的方案的期望之和。 考虑 (i,fa) 这条边插入的位置如果在 j 之前那 rt 将直接从第 j 条边开始受影响否则再枚举这条边插入的位置此时 rt 的存活收到 (i,fa) 这条边的影响期望要除二。因此有转移 gi,j(sizi−j)dpi,j12∑k0j−1dpi,kg_{i,j}(siz_i-j)dp_{i,j}\frac 1 2\sum_{k0}^{j-1}dp_{i,k}gi,j(sizi−j)dpi,j21k0∑j−1dpi,k 不难发现各个儿子之间是互不影响的只要保证 rt 进入子树前后的边顺序不会颠倒即可就是一个简单的组合数。 n50n50n50 这样的范围可以直接用 double 算组合数。
代码
//luogu
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N105;
const int mod1e97;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;
vectorinte[N];
double c[N][N],bas;
void init(){c[0][0]1;for(int i1;in;i){c[i][0]1;for(int j1;ji;j) c[i][j]c[i-1][j-1]c[i-1][j];}bas1;for(int i1;in;i) basbas*i;return;
}double dp[N][N],g[N][N],tmp[2][N];
int siz[N];
void dfs(int x,int fa){for(int to:e[x]){if(tofa) continue;dfs(to,x);}siz[x]0;memset(tmp,0,sizeof(tmp));int now1,pre0;tmp[now][0]1;for(int to:e[x]){if(tofa) continue;//printf( %d - %d\n,x,to);swap(now,pre);memset(tmp[now],0,sizeof(tmp[now]));for(int i0;isiz[to];i){g[to][i](siz[to]-i)*dp[to][i];for(int j0;ji;j) g[to][i]dp[to][j]/2;//printf( i%d g%4lf\n,i,g[to][i]);}for(int i0;isiz[to];i){for(int j0;jsiz[x];j){tmp[now][ij]g[to][i]*tmp[pre][j]*c[ij][i]*c[siz[to]-isiz[x]-j][siz[to]-i];}}siz[x]siz[to];}siz[x];for(int i0;isiz[x];i){dp[x][i]tmp[now][i];//printf(x%d i%d dp%.4lf\n,x,i,dp[x][i]);}return;
}signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifnread();for(int i1;in;i){int xread(),yread();e[x].push_back(y);e[y].push_back(x);}init();for(int x1;xn;x){memset(dp,0,sizeof(dp));memset(g,0,sizeof(g));dfs(x,0);printf(%.8lf\n,dp[x][n-1]/bas);}return 0;
}
