题解：P10140 [USACO24JAN] Island Vacation P
tobie
·
·
题解
考虑拆分一次游走过程：我们定义“一次操作”为在 u 处进行一次判定后发现没有结束，然后从 u 走到 v。
设当前状态下 u 的出度为 d，则该次操作的贡献为 \dfrac {(1-p_u)} d。
以下 dp 过程中使用“概率”一词似乎并不是非常恰当，我们认为一条路径的“权值”为每次操作的贡献的乘积。自然想到设 f_u 表示所有第一次走到 u 的路径的权值和。
首先建出圆方树。对于一个节点 u，如果我们钦定最后在 u 节点停下，则我们的过程必然会分为如下阶段：
- 首先我们要走到 u，贡献为 f_u。
- 然后我们可能会穿过 u 节点子树内的若干个环回到 u 节点，然后再下一次操作的“判定”时倒闭。
这里我们发现从 u 出发穿过一个环然后回到 u 的过程也是很重要的。结合以上分析，我们定义如下状态：
-
-
-
现在考虑计算 $h_u$。
假设我们从 $u$ 节点出发，选择了 $S$ 中的方点对应的环，最后回到 $u$ 节点的贡献差不多长成这个样子：
$$\frac {d_0^{|S|} d_0!!|S|!}{(d_0-2|S|)!!}\prod_{v\in S} g_v$$
解释一下意思：每个环的贡献显然就是 $g_v$，先乘上，然后考虑修正。
每次从 $u$ 出发时，$u$ 的出度分别为 $d_0,d_0-2,d_0-4,\cdots$，而 $g_v$ 里的贡献为 $\frac 1 d$，所以需要乘上 $\frac d {d_0-2k}$ 的修正项；$S$ 中元素没有顺序还会带来 $|S|!$ 的贡献；
你发现我们只在乎选取的集合的 $|S|$ 和 $\prod g_v$，跑一遍背包，然后带入公式计算即可。
写代码时发现这个式子还需要进行一些修补，比如需要考虑走完之后的那个红色的出边，以及 $u=1$ 时的 $d_0$ 和其他情况略有不同，需要特别注意。
计算 $g_u$ 和 $h_u$ 可以自底向上跑一遍 dfs。复杂度 $O(n^2)$。
- - -
接下来考虑如何计算 $f_u$。
如图。目前已知你第一次走到了 $u$，则你会先走绿色的环，然后颜色红色边走到 $v$，途中还可能经过一些蓝色的环。
蓝色的环贡献就是 $h_x$，红色边可以直接计算，现在只需要考虑绿色边。
我们发现，可以选的绿色圈的集合 $S_0$ 是 $u$ 子树内所有可以选择的圈的集合 $S$ 去掉当前这个环，所以跑一个撤销背包即可，式子同上。
至于答案的计算，你只需要把 $f_u$ 和 $h_u$ 拼起来就行了。
综上，总复杂度为 $O(n^2)$，瓶颈在背包。可以用分治 NTT 做到 $O(n \log ^2 n)$，懒得写了，就这样吧。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=20009;
const int mod=1e9+7;
int inv[N];
int n,ncnt=0,a[N],deg[N];
vector<int> to[N];
int siz[N];
namespace Build{
vector<int> G[N];
int m;
int dfn[N],low[N],dfncnt=0;
int sta[N],tp=0;
void dfs(int u,int f)
{
dfn[u]=low[u]=++dfncnt;
sta[++tp]=u;
for(int v:G[u])
if(!dfn[v])
{
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]==dfn[u])
{
ncnt++;
to[ncnt].push_back(u);
to[u].push_back(ncnt);
siz[ncnt]=1;
for(int x=0;x!=v;tp--)
{
x=sta[tp];
to[ncnt].push_back(x);
to[x].push_back(ncnt);
siz[ncnt]++;
}
}
}
else low[u]=min(low[u],dfn[v]);
}
void ReadIn()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n*2;i++) to[i].clear(),G[i].clear(),siz[i]=0;
for(int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
G[u].push_back(v),G[v].push_back(u);
}
for(int i=1;i<=n*2;i++) dfn[i]=low[i]=0;
dfncnt=0,tp=0;
for(int i=1;i<=n;i++) deg[i]=G[i].size();
ncnt=n;
dfs(1,0);
}
}
using Build::ReadIn;
int g[N],h[N];
void dfs1(int u,int f)
{
if(u>n)
{
g[u]=2ll*(mod+1-a[f])*inv[deg[f]]%mod;
for(int v:to[u])
if(v!=f)
{
dfs1(v,u);
g[u]=1ll*g[u]*h[v]%mod;
}
}
else
{
for(int v:to[u]) if(v!=f) dfs1(v,u);
vector<int> tmp; tmp.push_back(1);
for(int v:to[u])
if(v!=f&&siz[v]>2)
{
tmp.push_back(0);
for(int i=(int)(tmp.size())-1;i;i--)
tmp[i]=(1ll*tmp[i-1]*g[v]+tmp[i])%mod;
}
int d1=deg[u],d2=deg[u]-(f!=0),s1=(mod+1-a[u])%mod;
for(int i=0;i<tmp.size();i++)
{
h[u]=(h[u]+1ll*tmp[i]*s1%mod*inv[d2])%mod;
s1=1ll*s1*d1%mod*inv[d2]%mod*(i+1)%mod;
d2-=2;
}
}
}
int f[N],ans[N];
void dfs2(int u,int fa)
{
vector<int> tmp; tmp.push_back(1);
for(int v:to[u])
if(v!=fa&&siz[v]>2)
{
tmp.push_back(0);
for(int i=(int)(tmp.size())-1;i;i--)
tmp[i]=(1ll*tmp[i-1]*g[v]+tmp[i])%mod;
}
int d1=deg[u], d2=deg[u]-(fa!=0), s1=1;
for(int i=0;i<tmp.size();i++)
{
ans[u]=(ans[u]+1ll*tmp[i]*(d2==0?1:a[u])%mod*s1)%mod;
s1=1ll*s1*d1%mod*inv[d2]%mod*(i+1)%mod;
d2-=2;
}
ans[u]=1ll*ans[u]*f[u]%mod;
for(int vv:to[u])
if(vv==fa) continue;
else if(siz[vv]==2)
{
for(int v:to[vv])
if(v!=u)
{
d1=deg[u], d2=deg[u]-(fa!=0), s1=1ll*f[u]*(mod+1-a[u])%mod;
for(int i=0;i<tmp.size();i++)
{
f[v]=(f[v]+1ll*tmp[i]*s1%mod*inv[d2])%mod;
s1=1ll*s1*d1%mod*inv[d2]%mod*(i+1)%mod;
d2-=2;
}
dfs2(v,vv);
}
}
else
{
vector<int> tmp2=tmp;
for(int i=1;i<tmp.size();i++)
tmp[i]=(tmp[i]+1ll*(mod-g[vv])*tmp[i-1])%mod;
tmp.pop_back();
int coaf=1ll*f[u]*(mod+1-a[u])%mod;
for(int i=1;i<to[vv].size();i++)
{
d1=deg[u], d2=deg[u]-(fa!=0), s1=coaf;
for(int j=0;j<tmp.size();j++)
{
(f[to[vv][i]]+=1ll*tmp[j]*s1%mod*inv[d2]%mod)%=mod;
s1=1ll*s1*d1%mod*inv[d2]%mod*(j+1)%mod;
d2-=2;
}
coaf=1ll*coaf*h[to[vv][i]]%mod;
}
coaf=1ll*f[u]*(mod+1-a[u])%mod;
for(int i=(int)(to[vv].size())-1;i>=1;i--)
{
d1=deg[u], d2=deg[u]-(fa!=0), s1=coaf;
for(int j=0;j<tmp.size();j++)
{
(f[to[vv][i]]+=1ll*tmp[j]*s1%mod*inv[d2]%mod)%=mod;
s1=1ll*s1*d1%mod*inv[d2]%mod*(j+1)%mod;
d2-=2;
}
coaf=1ll*coaf*h[to[vv][i]]%mod;
}
swap(tmp,tmp2);
for(int v:to[vv]) if(v!=u) dfs2(v,vv);
}
}
void work()
{
ReadIn();
for(int i=1;i<=ncnt;i++) f[i]=g[i]=h[i]=ans[i]=0;
dfs1(1,0);
f[1]=1;
dfs2(1,0);
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
puts("");
}
signed main()
{
int T;
scanf("%d",&T);
inv[0]=inv[1]=1;
for(int i=2;i<=20000;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
while(T--) work();
}
```