JZOJ 4225. 【五校聯考3day1】寶藏
題目
Description
Input
Output
Sample Input
2
3
1 0
1 2
2
1 0 1
2 0 2 1
4
0 1
2 0
3 0
1
3 0 1 0 1
Sample Output
1.0000
5.0000
<空行>
11.0000
Data Constraint
題解
- 這是一個樹上随機遊走的問題。
- 題目可以簡化為：從一個節點出發，等機率地向它所連的點走去，每條邊權均為 1 1 1。求從起點按順序經過的一系列節點後到達終點的期望路徑長度。
- 首先我們把問題中的路線拆分為以下兩種：
- 1、 F ( x ) F(x) F(x)表示從 x x x走向 f a t h e r [ x ] father[x] father[x]，記錄 f [ x ] f[x] f[x]表示其期望路徑長度；
- 2、 G ( x ) G(x) G(x)表示從 f a t h e r [ x ] father[x] father[x]走向 x x x，記錄 g [ x ] g[x] g[x]表示其期望路徑長度。
- 問題中的路徑就是若幹條上面兩種的路徑總和，總的期望值也就是每一段的期望值總和。
- 現在考慮怎麼計算 f [ x ] f[x] f[x]和 g [ x ] g[x] g[x]？
- 先令 d e g [ x ] deg[x] deg[x]表示 x x x的度數， s o n [ x ] son[x] son[x]表示 x x x的子節點集合。
-
計算 f [ x ] f[x] f[x]的方程如下：
-
可以直接走到 f a t h e r [ x ] father[x] father[x]，也可以經過它的兒子再走到 f a t h e r [ x ] father[x] father[x]。
f [ x ] = 1 + ∑ v ∈ s o n [ x ] f [ v ] + f [ x ] + 1 d e g [ x ] f[x]=\frac{1+\displaystyle \sum _{v\in son[x]}f[v]+f[x]+1}{deg[x]} f[x]=deg[x]1+v∈son[x]∑f[v]+f[x]+1
< = > f [ x ] ∗ d e g [ x ] = 1 + ∑ v ∈ s o n [ x ] f [ v ] + f [ x ] + 1 <=>f[x]*deg[x]=1+\displaystyle \sum _{v\in son[x]}f[v]+f[x]+1 <=>f[x]∗deg[x]=1+v∈son[x]∑f[v]+f[x]+1
< = > f [ x ] ∗ d e g [ x ] = d e g [ x ] + ( d e g [ x ] − 1 ) ∗ f [ x ] + ∑ v ∈ s o n [ x ] f [ v ] <=>f[x]*deg[x]=deg[x]+(deg[x]-1)*f[x]+\displaystyle \sum _{v\in son[x]}f[v] <=>f[x]∗deg[x]=deg[x]+(deg[x]−1)∗f[x]+v∈son[x]∑f[v]
< = > f [ x ] = d e g [ x ] + ∑ v ∈ s o n [ x ] f [ v ] <=>f[x]=deg[x]+\displaystyle \sum _{v\in son[x]}f[v] <=>f[x]=deg[x]+v∈son[x]∑f[v]
-
計算 g [ x ] g[x] g[x]的方程如下：
-
可以直接走到 x x x，也可以先走到 f a t h e r [ f a t h e r [ x ] ] father[father[x]] father[father[x]]，也可能走到 x x x的兄弟。
g [ x ] = 1 + ( 1 + g [ x ] + g [ f a t h e r [ x ] ] ) + ∑ v ∈ s o n [ f a t h e r [ x ] ] ∩ v ≠ x f [ v ] + g [ x ] + 1 d e g [ f a t h e r [ x ] ] g[x]=\frac{1+(1+g[x]+g[father[x]])+\displaystyle \sum _{{v\in son[father[x]]}∩{v≠x}}f[v]+g[x]+1}{deg[father[x]]} g[x]=deg[father[x]]1+(1+g[x]+g[father[x]])+v∈son[father[x]]∩v=x∑f[v]+g[x]+1
< = > g [ x ] ∗ d e g [ f a t h e r [ x ] ] = 2 + g [ x ] + g [ f a t h e r [ x ] ] + ∑ v ∈ s o n [ f a t h e r [ x ] ] ∩ v ≠ x f [ v ] + g [ x ] + 1 <=>g[x]*deg[father[x]]=2+g[x]+g[father[x]]+\displaystyle \sum _{{v\in son[father[x]]}∩{v≠x}}f[v]+g[x]+1 <=>g[x]∗deg[father[x]]=2+g[x]+g[father[x]]+v∈son[father[x]]∩v=x∑f[v]+g[x]+1
< = > g [ x ] ∗ d e g [ f a t h e r [ x ] ] = d e g [ f a t h e r [ x ] ] + g [ x ] ∗ ( d e g [ f a t h e r [ x ] ] − 1 ) <=>g[x]*deg[father[x]]=deg[father[x]]+g[x]*(deg[father[x]]-1) <=>g[x]∗deg[father[x]]=deg[father[x]]+g[x]∗(deg[father[x]]−1)
+ g [ f a t h e r [ x ] ] + ∑ v ∈ s o n [ f a t h e r [ x ] ] ∩ v ≠ x f [ v ] +g[father[x]]+\displaystyle \sum _{{v\in son[father[x]]}∩{v≠x}}f[v] +g[father[x]]+v∈son[father[x]]∩v=x∑f[v]
< = > g [ x ] = d e g [ f a t h e r [ x ] ] + g [ f a t h e r [ x ] ] + ∑ v ∈ s o n [ f a t h e r [ x ] ] ∩ v ≠ x f [ v ] <=>g[x]=deg[father[x]]+g[father[x]]+\displaystyle \sum _{{v\in son[father[x]]}∩{v≠x}}f[v] <=>g[x]=deg[father[x]]+g[father[x]]+v∈son[father[x]]∩v=x∑f[v]
- 于是這樣就可以把所有的 f [ x ] f[x] f[x]和 g [ x ] g[x] g[x]計算出來了。
- 記得其中 f [ x ] = g [ x ] = 0 f[x]=g[x]=0 f[x]=g[x]=0.
- 如果一步一步地走，會時間超限，
- 自然想到用倍增 L C A LCA LCA.
代碼
#include<cstdio>
#include<cstring>
using namespace std;
int last[50010],next[100010],tov[100010],len=0;
int deep[50010],deg[50010];
int f[50010],g[50010],e[17],tn;
struct node
{
int f,g,to;
}q[50010][17];
void add(int x,int y)
{
tov[++len]=y;
next[len]=last[x];
last[x]=len;
}
void dfs(int x,int fa)
{
f[x]=deg[x];
for(int i=last[x];i;i=next[i]) if(tov[i]!=fa)
{
deep[tov[i]]=deep[x]+1;
dfs(tov[i],x);
f[x]+=f[tov[i]];
}
}
void dfs1(int x,int sum,int fa)
{
if(x>1) g[x]=g[fa]+deg[fa]+sum-f[x];
int ss=0;
for(int i=last[x];i;i=next[i]) if(tov[i]!=fa) ss+=f[tov[i]];
for(int i=last[x];i;i=next[i]) if(tov[i]!=fa) dfs1(tov[i],ss,x);
}
void dfs2(int x,int fa)
{
q[x][0].to=fa,q[x][0].f=f[x],q[x][0].g=g[x];
for(int i=1;i<=16;i++)
{
q[x][i].to=q[q[x][i-1].to][i-1].to;
q[x][i].f=q[x][i-1].f+q[q[x][i-1].to][i-1].f;
q[x][i].g=q[x][i-1].g+q[q[x][i-1].to][i-1].g;
}
for(int i=last[x];i;i=next[i]) if(tov[i]!=fa) dfs2(tov[i],x);
}
int main()
{
int n,i,j,k,x,y,qs,p;
scanf("%d",&tn);
e[0]=1;
for(i=1;i<=16;i++) e[i]=e[i-1]*2;
while(tn--)
{
scanf("%d",&n);
memset(last,0,sizeof(last));
memset(deg,0,sizeof(deg));
len=0;
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
x++,y++;
deg[x]++,deg[y]++;
add(x,y);add(y,x);
}
deep[1]=0;
memset(g,0,sizeof(g));
memset(f,0,sizeof(f));
dfs(1,0);
dfs1(1,0,0);
dfs2(1,0);
scanf("%d",&qs);
for(i=1;i<=qs;i++)
{
scanf("%d",&p);
int la,no;
scanf("%d",&la);
la++;
int ans=0;
for(j=2;j<=p+1;j++)
{
scanf("%d",&no);
no++;
x=la,y=no;
if(deep[x]>deep[y])
{
for(k=16;k>=0;k--) if(deep[x]-e[k]>=deep[y])
{
ans+=q[x][k].f;
x=q[x][k].to;
}
}
else
{
for(k=16;k>=0;k--) if(deep[y]-e[k]>=deep[x])
{
ans+=q[y][k].g;
y=q[y][k].to;
}
}
if(x!=y)
{
for(k=16;k>=0;k--) if(q[x][k].to!=q[y][k].to)
{
ans+=q[x][k].f+q[y][k].g;
x=q[x][k].to;
y=q[y][k].to;
}
ans+=q[x][0].f+q[y][0].g;
}
la=no;
}
printf("%d.0000\n",ans);
}
printf("\n");
}
return 0;
}