tree | Hexo

归档于 2019-09-25 18:19

随机走,看期望

由于zzn过于sb,考试推出来式子因为统计时间不对没有$AC$(应dfs前统计)

zzn实在过于sb,式子和题解完全不一样,所以看题解的可以走了

记录tofa[x]表示当前点走到父亲期望步数

可以直接走到父亲 贡献$\frac{1}{deg[x]}$

走到儿子再走到父亲$\frac{1}{deg[x]}*(1+tofa[y]+tofa[x])
$解释一下,花一步走到$y$,花$tofa[y]$走到$x$最后还是要走到$fa$

总$tofa[x]=\frac{1}{deg[x]}+\sum\limits_{y}^{y\in son[x]} \frac{1}{deg[x]}
(1+tofa[y]+tofa[x])$

记录toson[x]表示从父亲走到x步数

考虑toson[y]转移

从$x$直接走到$y$ $\frac{1}{deg[x]}$

走到$x$父亲再走到$y$ $\frac{1}{deg[x]}*(toson[x]+1+toson[y])$

走到$y$兄弟走到$y$ $\frac{1}{deg[x]}*(1+tofa[y]+toson[y])$

总$toson[y]=\frac{1}{deg[x]}+\frac{1}{deg[x]}*(toson[x]+1+toson[y])
+\sum\limits_{y2}^{y2\in son[x] & y2!=y} *(1+tofa[y2]+toson[y])$

然后移项

$tofa[x]=deg[x]+\sum\limits_{y}^{y\in son[x]}tofa[y]$

$toson[y]=deg[x]+toson[x]+\sum\limits_{y2}^{y2\in son[x] & y2!=y} tofa[y2]$

统计即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 222222
ll n,tot,canqj;
ll vis[A],nxt[A],head[A],ver[A];
double f[A],dis[A],tofa[A],toson[A],deg[A];
void add(ll x,ll y){
    nxt[++tot]=head[x],head[x]=tot,ver[tot]=y;
}
void dfs(ll x,ll pre){
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==pre) continue ;
        f[y]=2+f[x];
        dis[y]=dis[x]+f[x];
        dfs(y,x);
    }
}
void dpfs1(ll x,ll pre){
    tofa[x]=deg[x];
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==pre) continue ;
        dpfs1(y,x);
        tofa[x]+=tofa[y];
    }
//    printf("tofa[%lld]=%.3lf\n",x,tofa[x]);
}
void dpfs2(ll x,ll pre){
    ll sum=0;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==pre) continue ;
        toson[y]=deg[x]+toson[x];
        sum+=tofa[y];
//        printf("toson[%lld]=%.3lf\n",y,toson[y]);
    }
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==pre) continue ;
        toson[y]+=sum-tofa[y];
//        printf("toson[%lld]=%.3lf\n",y,toson[y]);
    }
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==pre) continue ;
        dpfs2(y,x);
    }
}
void dfs3(ll x,ll pre){
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==pre) continue ;
        dis[y]=dis[x]+toson[y];
        dfs3(y,x);
        
//        printf("dis[%lld]=%.3lf  dis[%lld]=%.3lf\n",y,dis[y],x,dis[x]);
    }
}
int main(){
    scanf("%lld",&n);
    f[1]=1;
    dis[1]=1;
    canqj=1;
    for(ll i=1,a,b;i<n;i++){
        scanf("%lld%lld",&a,&b);
        add(a,b);add(b,a);
        deg[a]++,deg[b]++;
        if(deg[a]>2||deg[b]>2) canqj=0;
    }
/*    dfs(1,0);
    for(ll i=1;i<=n;i++){
        printf("%.3lf\n",dis[i]);
    }        
*/    for(ll i=head[1];i;i=nxt[i]){
        ll y=ver[i];
        toson[y]=1;
    }
    for(ll i=2;i<=n;i++){
        if(deg[i]==1){
            tofa[i]=1;
        }
    }
//    memset(dis,0,sizeof(dis));
    dis[1]=1;
    dpfs1(1,0);
    dpfs2(1,0);
    dfs3(1,0);
    for(ll i=1;i<=n;i++){
        printf("%.3lf\n",dis[i]);
    }
//    }
}

View Code