duoxiao OJ #910 【高手训练】【动态规划】梦中漫步期望 LCA

LINK：梦中漫步

当然也可以去一本通的Oj/loj上交(loj可能没有..

期望好题。期望和dp往往是在一起的。

前置知识：1. 期望是线性可加的。2.和的期望等于期望的和.

从u出发每次随机选一条边走问走到v的期望经过的边数。

寒假的时候就在思考这道题了当时yy了一个LCA乱搞的方法 wa的不省人事。

重新分析：考虑设\(f_i\)表示从u出发到i这个点的期望经过的边数。

列出转移发现转移有环暴力高斯消元显然不可行。

刚才列出的两个知识和的期望等于期望的和。

这个东西告诉我们 u->v的期望边数=u->fu->ffu->fffu->...v的期望边数。

于是可以设出两个期望数组.

\(f1_x\)表示由x到fx的经过的期望边数。\(f2_x\)表示fx到x的期望边数。

只要求出这个两个数组我们就可以利用求出LCA 求出路径上的这两个数组的和得到答案。

考虑\(f1\)怎么求设d表示x的度数\(f1_x=\frac{1}{d}+\sum_{v\in son_x}\frac{1}{d}(1+f1_v+f1_x)\)

化简可得 \(f1_x=d+\sum_{v\in son_x}f1_v\)

考虑\(f2\) 设d表示x的父亲的度数\(f2_x=\frac{1}{d}+\frac{1}{d}(1+f2_{fa}+f2_x)+\sum_{v\in son_x,v\neq x}\frac{1}{d}(1+f1_v+f2_x)\)

化简可得 \(f2_x=d+f2_{fa}+\sum_{v\in son_x,v\neq x}f1_v\)

然后树上取前缀和求LCA即可O(1)计算答案。

复杂度Qlogn.

const int MAXN=100010;

int n,Q,len;

int du[MAXN],d[MAXN];

int f[MAXN][20],Log[MAXN];

ll f1[MAXN],ans,f2[MAXN];//f1[x]表示由x走到fx的期望边数.f2[x]表示由fx走到x的期望边数.

int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];

inline void add(int x,int  y)

{

	ver[++len]=y;

	nex[len]=lin[x];

	lin[x]=len;++du[y];

}

inline void dfs(int x,int fa)

{

	f[x][0]=fa;d[x]=d[fa]+1;

	rep(1,Log[d[x]],i)f[x][i]=f[f[x][i-1]][i-1];

	f1[x]=du[x];

	go(x)if(tn!=fa)dfs(tn,x),f1[x]=(f1[x]+f1[tn])%mod;

}

inline void dp(int x,int fa)

{

	if(x!=1)f2[x]=((f2[fa]+f1[fa]-f1[x])%mod+mod)%mod;

	go(x)if(tn!=fa)dp(tn,x);

}

inline void dfs(int x)

{

	go(x)if(tn!=f[x][0])f1[tn]=(f1[tn]+f1[x])%mod,f2[tn]=(f2[tn]+f2[x])%mod,dfs(tn);

}

inline int LCA(int x,int y)

{

	if(d[x]>d[y])swap(x,y);

	for(int i=Log[d[y]];i>=0;--i)

		if(d[f[y][i]]>=d[x])y=f[y][i];

	if(x==y)return x;

	for(int i=Log[d[x]];i>=0;--i)

		if(f[x][i]!=f[y][i])

			x=f[x][i],y=f[y][i];

	return f[x][0];

}

int main()

{

	freopen("1.in","r",stdin);

	//freopen("wanderindream.in","r",stdin);

	//freopen("wanderindream.out","w",stdout);

	n=read();Q=read();

	for(int i=2;i<=n;++i)

	{

		int x,y;

		x=read();y=read();

		add(x,y);add(y,x);

		Log[i]=Log[i>>1]+1;

	}

	dfs(1,0);dp(1,0);dfs(1);

	for(int i=1;i<=Q;++i)

	{

		int x,y;

		x=read();y=read();

		if(x==y){puts("0");continue;}

		int lca=LCA(x,y);

		ans=f1[x]-f1[lca];

		ans=(ans+f2[y]-f2[lca])%mod;

		ans=(ans+mod)%mod;

		putl(ans);

	}

	return 0;

}

非常妙的期望。

巴特西

duoxiao OJ #910 【高手训练】【动态规划】梦中漫步期望 LCA

最新文章

热门文章

巴特西

duoxiao OJ #910 【高手训练】【动态规划】梦中漫步 期望 LCA

最新文章

热门文章

duoxiao OJ #910 【高手训练】【动态规划】梦中漫步期望 LCA