求助！！！调了一天了

题目描述 梦游中的你来到了一棵 N 个节点的树上. 你一共做了 Q 个梦, 每个梦需要你从点 u 走到 点 v 之后才能苏醒, 由于你正在梦游, 所以每到一个节点后,你会在它连出去的边中等概率地 选择一条走过去, 为了确保第二天能够准时到校, 你要求出每个梦期望经过多少条边才能苏 醒. 为了避免精度误差, 你要输出答案模10^9 + 7的结果.

输入格式 第一行两个整数分别代表 N 和 Q. 接下来 N-1 行, 每行两个整数 u, v 代表树中的一条边. 接下来 Q 行, 每行两个整数代表询问的 u,v.

输出格式 一共 Q 行, 每行一个整数代表答案

样例 样例输入 4 2 1 2 2 3 3 4 1 4 3 4 样例输出 9 5 数据范围与提示 对于 20%的数据, N <= 10. 对于 40%的数据, N <= 1000. 另有 20%的数据, 保证给定的树是一条链. 对于 100%的数据, N <= 100000, Q <= 100000.

求助为什么我$dfs2$求出$f[i]$数组

$f[now]=d[now]+\sum{f[son]}$

inline void dfs10(int now,int fa){
    if(siz[now]==1) {
        f[now]=1;
        return ;
    }

    f[now]=0;
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        
        // f[now]+=( (double)((double)(d[now]-1)/(double)d[now])*(1+f[y]+f[now]) );
        // f[now]+=((d[now]-1)+(d[now]-1)*f[y]);
        dfs2(y,now);
        if(now!=1)
        f[now]+=(f[y]+1),
        f[now]%=mod;
        
    }
    f[now]++;
}

这样写是对的AC

但是

inline void dfs2(int now,int fa){
    if(siz[now]==1) {
        f[now]=1;
        return ;
    }

    f[now]=g[now];
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        
        // f[now]+=( (double)((double)(d[now]-1)/(double)d[now])*(1+f[y]+f[now]) );
        // f[now]+=((d[now]-1)+(d[now]-1)*f[y]);
        dfs2(y,now);
        if(now!=1)
        f[now]+=(f[y]),
        f[now]%=mod;
        
    }
}

这样就WA 了？

球球跌教教我把，跳了一天了

$dfs3$求$g[i]$也错了

详见正确：$dfs9$

和错误:$dfs3$

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
    inline int read(){
        int f(1),x(0);
        char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
        return f*x;
    }
    inline void Write(int x){
        if(x>9) Write(x/10);
        putchar(x%10+48);
    }
    inline void write(int x){
        if(x<0) putchar('-'),x=-x;
        Write(x);
        putchar('\n');
    }
}
using namespace Testify;
const int N=1e5+5;
int n,m,T,d[N];
int head[N],nxt[N<<1],to[N<<1],tot(0),t;
int dep[N],cnt(0),num(0),siz[N],fate[N][20];
int f[N],g[N];//f是自己走到父亲节点の期望，g是父亲走到当前的期望
                //dfs后f更新成当前节点到根
const int mod=1e9+7;
inline void add(int x,int y){
    to[++tot]=y,nxt[tot]=head[x],head[x]=tot;
    return ;
}
inline void dfs1(int now,int fa){
    dep[now]=dep[fa]+1;
    fate[now][0]=fa;
    siz[now]=1;
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs1(y,now);
        siz[now]+=siz[y];
    }
}
inline int lca(int x,int y){
    if(dep[x]>dep[y]) swap(x,y);
    //现在让y比x深
    for(register int i=t;i>=0;i--){
        if(dep[fate[y][i]]>=dep[x]){
            y=fate[y][i];
        }
    }//深度一样力
    if(x==y) return x;
    for(register int i=t;i>=0;i--){
        if(fate[x][i]!=fate[y][i]){
            x=fate[x][i];
            y=fate[y][i];
        }
    }//在深度相同的时候向上跳到只差一步就获得lca
    return fate[x][0];
}


inline void dfs2(int now,int fa){
    if(siz[now]==1) {
        f[now]=1;
        return ;
    }
    // if(now!=1)

    f[now]=d[now];
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        
        // f[now]+=( (double)((double)(d[now]-1)/(double)d[now])*(1+f[y]+f[now]) );
        // f[now]+=((d[now]-1)+(d[now]-1)*f[y]);
        dfs2(y,now);
        if(now!=1)
        f[now]+=(f[y]),
        f[now]%=mod;
        
    }
}
inline void dfs10(int now,int fa){
    if(siz[now]==1) {
        f[now]=1;
        return ;
    }
    // if(now!=1)

    f[now]=0;
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        
        // f[now]+=( (double)((double)(d[now]-1)/(double)d[now])*(1+f[y]+f[now]) );
        // f[now]+=((d[now]-1)+(d[now]-1)*f[y]);
        dfs10(y,now);
        if(now!=1)
        f[now]+=(f[y]+1),
        f[now]%=mod;
        
    }
    f[now]++;
}


//求助

inline void dfs3(int now,int fa){//先用这个再dfs4合并f
    int sum=0;
    if(siz[now]!=1){
        sum=g[now]+d[now];
        sum%=mod;
        for(register int i=head[now];i;i=nxt[i]){
            int y=to[i];
            if(y==now) continue;
            sum+=f[y];
            sum%=mod;
        }
        for(register int i=head[now];i;i=nxt[i]){
            int y=to[i];
            if(y==fa) continue;
            // if(siz[y]!=1){
                g[y]+=((sum-f[y])%mod+mod)%mod;
                g[y]%=mod;
            // }
            
            dfs3(y,now);
        }
    }
    else{//叶子节点
        g[now]=((2+g[fa])/(d[fa]-1));
    }
}
inline void dfs9(int now,int fa){
    int sum(0);
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) {
            sum+=(g[now]+1);
            sum%=mod;
        }
        else{
            sum+=(f[y]+1)%mod;
        }
    }
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        g[y]=((sum-f[y])%mod+mod)%mod;
        dfs9(y,now);
    }
}



inline void dfs4(int now,int fa){
    f[now]+=f[fa];
    f[now]%=mod;
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs4(y,now);
    }
}
inline void dfs5(int now,int fa){
    g[now]+=g[fa];
    g[now]%=mod;
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs5(y,now);
    }
}
inline void dfs6(int now,int fa){
    if(siz[now]==1) g[now]=0;
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs6(y,now);
    }
}
inline void dfs7(int now,int fa){
    if(now!=1) g[now]=g[fa]+f[fa]-f[now];
    for(register int i=head[now];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs7(y,now);
    }
}


inline void dfs8(int now,int fa){
    cerr<<"稍比我册匿门嫲"<<endl;
}
inline int dis(int x,int y){
    int Lca=lca(x,y);
    return ((f[x]+g[y]-f[Lca]-g[Lca])%mod+mod)%mod;
}
signed main(void){
    n=read(),T=read();
    t=log2(n)+1;
    for(register int i=1;i<n;i++){
        register int asd=read(),jkl=read();
        add(asd,jkl),add(jkl,asd);
        d[asd]++,d[jkl]++;
    }
    dfs1(1,0);
    
    for(register int j=1;j<=t;j++){
        for(register int i=1;i<=n;i++){
            fate[i][j]=fate[fate[i][j-1]][j-1];
        }
    }
    //这道题woの思路是
    //求出来u到v的lca
    //算出来每个节点到根节点的期望然后随便求一下就行力????？

    //算出来每个节点到父亲节点的期望，再求出每个点到根节点的期望?
    // dfs2(1,0);
    dfs10(1,0);
    f[1]=0;
    // for(register int i=1;i<=n;i++)
    // cerr<<i<<" :"<<f[i]<<" ";
    // cerr<<endl<<endl;

    // dfs3(1,0);
    dfs9(1,0);
    // for(register int i=1;i<=n;i++)
    // cerr<<i<<" :"<<g[i]<<" ";
    // cerr<<endl<<endl;

    // dfs7(1,0);
    // for(register int i=1;i<=n;i++){
    //     cerr<<g[i]<<" ";
    // }
    // cerr<<endl;
    dfs4(1,0);

    dfs5(1,0);
    dfs8(1,0);
    while(T--){
        int a=read(),b=read();
        write(dis(a,b));
    }
    
    return 0;
}

球球跌了😭😭😭😭😭😭