[DP记录]AT3721 [ARC086C] Smuggling Marbles
command_block
2021-05-12 07:38:03
**题意** ： 给出一棵 $n+1$ 个点的树，编号 $0\sim n$ ，其中0为根。
每个点上有 $0$ 或 $1$ 个石子，重复进行如下操作直至整棵树没有石子：
- 把 $0$ 上面的石子从树上拿走放入口袋。
- 把每个点上的石子移到其父亲上。
- 对于每个点，若其石子数 $≥2$，则移除该点所有石子（不放入口袋）。
求对于所有$2^{N+1}$种放置石子的方案，最终口袋中石子数的和为多少。答案对 $10^9+7$ 取模。
$n\leq 2\times 10^5$ ，时限$\texttt{3s}$。
------------
先考虑若给定石子放置方式如何求出口袋中的石子数。
不难发现，只有同深度的石子可能相遇，且对于每个深度最多只有可能收到一枚石子。
于是，可以对每层的节点分别考虑。
记 $dep_u$ 为 $u$ 的深度， $siz_u$ 为 $u$ 子树内节点数，$f_{u,d}$ 为 $u$ 子树内深度为 $d$ 的点合并到 $u$ 后，使得 $u$ 为 $1$ 的概率（方案数与总方案数只比）。
（若直接维护方案数，则需要更复杂的乘法标记）
边界 ： $f_{u,dep_u}=1/2$。
记 $u$ 的直接儿子为 $v_1,v_2,...v_m$ ，转移 ：
$$
f_{u,d}=\sum\limits_{i=1}^mf_{v_i,d}\prod_{j\neq i}(1-f_{v_j,d})
$$
最终 $f_{0,\_}$ 的和乘以 $2^{n+1}$ 即为答案。
可以使用长链剖分维护，复杂度 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxN 200500
using namespace std;
const int mod=1000000007,inv2=500000004;
vector<int> g[MaxN];
int len[MaxN],dep[MaxN],siz[MaxN],mp[MaxN];
void pfs(int u)
{
siz[u]=1;
for (int i=0,v;i<g[u].size();i++){
dep[v=g[u][i]]=dep[u]+1;
pfs(v);
siz[u]+=siz[v];
len[u]=max(len[u],len[v]+1);
if (len[v]>len[mp[u]])mp[u]=v;
}
}
int _o[MaxN<<1],*f[MaxN],*tf=_o,s[MaxN];
void dfs(int u,int fa)
{
f[u][dep[u]]=inv2;
if (!mp[u])return ;
f[mp[u]]=f[u];
dfs(mp[u],u);
int td=0;
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=mp[u]){
f[v]=tf-dep[v];tf+=len[v]+1;dfs(v,u);
td=max(td,len[v]);
}
for (int i=dep[u]+1;i<=dep[u]+td+1;i++)s[i]=1-f[u][i];
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=mp[u])
for (int k=dep[v];k<=dep[v]+len[v];k++){
f[u][k]=(1ll*s[k]*f[v][k]+1ll*f[u][k]*(1-f[v][k]))%mod;
s[k]=1ll*s[k]*(1-f[v][k])%mod;
}
}
int n;
int main()
{
scanf("%d",&n);
for (int i=2,fa;i<=n+1;i++){
scanf("%d",&fa);
g[fa+1].push_back(i);
}
len[0]=-1;pfs(1);
f[1]=tf;tf+=len[1]+1;dfs(1,0);
int ans=0;
for (int i=0;i<=len[1];i++)
ans=(ans+f[1][i])%mod;
for (int i=1;i<=n+1;i++)ans=(ans<<1)%mod;
printf("%d",(ans+mod)%mod);
return 0;
}
```