luogu P3412 仓鼠找sugar II 期望 树形dp

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

LINK：仓鼠找sugar II

以前做过类似的期望题目 加上最后的树形dp不算太难 还是可以推出来的。

容易发现 当固定起点和终点的时候 可以先固定根 这样就不用分到底是正着走还是倒着走了。

1为根 我们要求 x到y的期望步数.

由于期望的线性性 可以设出f[x]表示x到父亲的期望步数 g[x]表示父亲到儿子的期望步数。

很容易得到转移 不再赘述.

然后暴力找这条路径累加答案即可。

然后 就可以n^3的统计答案了 倍增优化一下就是n^2log的 考虑以每个点统计答案就发现可以n^2统计答案。

最后考虑树形dp 其实没必要每次统计一边答案 直接dp做。

总思想就是先统计所有x子树内所有点到x的贡献 x到自己子树内所有点的贡献。

最后是 x的子树互相跑的贡献 就可以做到O(n)了。

const int MAXN=100010;
int n,len;
int lin[MAXN],sz[MAXN],ver[MAXN<<1],nex[MAXN<<1],du[MAXN];
ll f[MAXN],g[MAXN],w[MAXN],s[MAXN],ans;
inline void add(int x,int y)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;++du[y];
}
inline ll ksm(ll b,ll p)
{
ll cnt=1;
while(p)
{
if(p&1)cnt=cnt*b%mod;
b=b*b%mod;
p=p>>1;
}
return cnt;
}
inline void dfs(int x,int fa)
{
f[x]=du[x];
go(x)if(tn!=fa)dfs(tn,x),f[x]=(f[x]+f[tn])%mod;
}
inline void dfs1(int x,int fa)
{
go(x)
if(tn!=fa)
{
g[tn]=(g[x]+f[x]-f[tn]+mod)%mod;
dfs1(tn,x);
}
}
inline void dp(int x,int fa)
{
sz[x]=1;w[x]=f[x];//w[x]表示x子树内的所有点走向x的父亲的期望步数.
s[x]=g[x];//s[x]表示x的父亲走向x子树内所有点的期望步数.
ll cnt1=0,cnt2=0,ss=0;
go(x)
{
if(tn==fa)continue;
dp(tn,x);
//统计子树两边互走的情况.
ans=(ans+cnt1*sz[tn]+s[tn]*ss)%mod;
ans=(ans+cnt2*sz[tn]+w[tn]*ss)%mod;
//先统计所有点到x的贡献.
ans=(ans+w[tn])%mod;
cnt1=(cnt1+w[tn])%mod;
w[x]=(w[x]+w[tn]+f[x]*sz[tn])%mod;
//再统计x到所有点的贡献.
ans=(ans+s[tn])%mod;
s[x]=(s[x]+s[tn]+g[x]*sz[tn])%mod;
cnt2=(cnt2+s[tn])%mod;
ss+=sz[tn];sz[x]+=sz[tn];
}
}
int main()
{
freopen("1.in","r",stdin);
get(n);
rep(2,n,i)
{
int x,y;
get(x);get(y);
add(x,y);add(y,x);
}
dfs(1,0);dfs1(1,0);
//rep(1,n,i)put(g[i]);
dp(1,0);putl(ans*ksm((ll)n*n%mod,mod-2)%mod);
return 0;
}