Tree1.0
Description
选择起始点和终点以后，会每次等概率随机走到一个相邻的点（不能来回走同一条边多次），问最后走到终点的期望步数
Solution
统计下子树内和子树外的点分别作为起点和终点的贡献即可
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100001;
struct node{
int to,ne;
}e[N<<1];
ll ans;
int SX,SY,X[N],Y[N],i,x,y,tot,h[N],sz[N],n;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void dfs(int u,int fa){
sz[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if ((v=e[i].to)!=fa){
dfs(v,u);
sz[u]+=sz[v];
X[u]+=X[v];
ans+=1ll*Y[u]*X[v]*sz[v];
}
ans+=1ll*Y[u]*(SX-X[u])*(n-sz[u]);
}
int main(){
n=rd();
for (i=1;i<n;i++) x=rd(),y=rd(),add(x,y),add(y,x);
for (i=1;i<=n;i++) SX+=(X[i]=rd()),SY+=(Y[i]=rd());
dfs(1,0);
printf("%.9lf",ans*1.0/SX/SY);
}
Tree2.0
Description
选择起始点和终点以后，会每次等概率随机走到一个相邻的点（随便怎么走），问最后走到终点的期望步数
Solution
f[i]表示i走到它父亲的期望步数
g[i]表示i父亲走到i的期望步数
首先叶子结点 f[i]都为 1。对于任意非叶子节点 i有 1/d[i]的概率走到父亲，还有 1/d[i]的概率走到各个儿子，所以 f[i]=1/d[i]+(f[son]+f[i]+1)/d[i]=>f[i]=d[i]+f[son]
同理 g[i]=1/d[fa]+(1+g[fa]+g[i])/d[fa]+(f[son]+g[i]+1)/d[fa]=>g[i]=d[fa]+g[fa]+f[son]（ son为 fa的儿子，且 son!=i）
然后对于每一条边，统计下子树内和子树外的点分别作为起点和终点的贡献即可
Code
#include<bits/stdc++.h>
using namespace std;
const int N=100001,M=998244353;
struct node{
int to,ne;
}e[N<<1];
int f[N],g[N],u,v,xx,yy,ans,sx,sy,x[N],y[N],h[N],tot,sum[N],p[N],n,i;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void ex_gcd(int a,int b,int &x,int &y){
if (!b) x=1,y=0;
else ex_gcd(b,a%b,y,x),y-=a/b*x;
}
void up(int u,int fa){
if (u!=1) f[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if ((v=e[i].to)!=fa) up(v,u),f[u]+=f[v]+1;
}
void down(int u,int fa){
for (int i=h[u],v;i;i=e[i].ne)
if ((v=e[i].to)!=fa) g[v]=f[u]-f[v]+g[u],down(v,u);
}
void dfs1(int u,int fa){
sum[u]=x[u];
for (int i=h[u],v;i;i=e[i].ne)
if ((v=e[i].to)!=fa) dfs1(v,u),sum[u]+=sum[v],p[u]=(p[u]+p[v]+1ll*sum[v]*f[v])%M;
}
void dfs2(int u,int fa){
ans=(ans+1ll*p[u]*y[u])%M;
for (int i=h[u],v;i;i=e[i].ne)
if ((v=e[i].to)!=fa) p[v]=(p[u]-1ll*sum[v]*f[v]%M+1ll*(sx-sum[v])*g[v]%M)%M,dfs2(v,u);
}
int main(){
n=rd();
for (i=1;i<n;i++) u=rd(),v=rd(),add(u,v),add(v,u);
for (i=1;i<=n;i++) x[i]=rd(),y[i]=rd(),sx+=x[i],sy+=y[i];
up(1,0);down(1,0);
dfs1(1,0);
dfs2(1,0);
ex_gcd(sx,M,xx,yy);
ans=1ll*ans*(xx+M)%M;
ex_gcd(sy,M,xx,yy);
ans=1ll*ans*(xx+M)%M;
printf("%d",(ans+M)%M);
}
京公网安备 11010502036488号