题解--AT3721 [ARC086C] Smuggling Marbles

· · 题解

因为每一轮操作都会把石子深度减 1，所以不同深度之间的石子之间是独立的。我们考虑对于同一个深度的石子，我们建出其虚树，因为只有在虚树节点上石子才可能发生合并。考虑进行 dp，设 f_{u,0/1} 为在虚树上 u 节点，在这里经过移除操作后剩余 0/1 个石子的方案数（只考虑本深度节点放与不放）。对答案的贡献即为 f_{rt,1}\times2^{n-c}，其中 rt 为虚树的根，c 为本深度节点个数。我们考虑转移。
对于 u，我们记录一个临时变量 f2，代表这里最后有 \ge 2 个石子的方案数。转移式为 f_{u,0}=f_{u,0}\times f_{v,0},f_{u,1}=f_{u,0}\times f_{v,1}+f_{u,0}\times f_{v,1},f2=f2\times(f_{v,0}+f_{v,1})+f_{u,1}\times f_{v,1}。（类似树上背包理解即可）最后将 f_{u,0}=f_{u,0}+f2。时间复杂度 O(n\log n)。 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int>::iterator iter;
const int maxn=2e5+5,mod=1e9+7;
struct edge {
    int next,to;
} e[maxn*2];
int h[maxn],cnt,d[maxn],f[maxn][18],lg2[maxn],n,m,p[maxn],pos,st[maxn],top,mxd;
bool bj[maxn];
ll ans,f0[maxn],f1[maxn];
vector<int> b[maxn],v[maxn];
void addedge(int x,int y) {
    e[++cnt].next=h[x],e[cnt].to=y,h[x]=cnt;
}
ll qpow(ll x,int y) {
    ll w=1;
    while(y) {
        if(y&1)w=w*x%mod;
        x=x*x%mod,y>>=1;
    }
    return w;
}
void dfs(int u,int fa) {
    mxd=max(mxd,d[u]=d[fa]+1),b[d[u]].push_back(u),f[u][0]=fa,p[u]=++pos;
    for(int i=1; i<=lg2[d[u]]; i++)f[u][i]=f[f[u][i-1]][i-1];
    for(int i=h[u]; i; i=e[i].next)dfs(e[i].to,u);
}
int lca(int x,int y) {
    if(d[x]<d[y])swap(x,y);
    while(d[x]>d[y])x=f[x][lg2[d[x]-d[y]]-1];
    if(x==y)return x;
    for(register int i=lg2[d[x]]-1; i>=0; i--)
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
void dp(int u) {
    ll f2=0;
    f0[u]=1,f1[u]=bj[u];
    for(iter it=v[u].begin(); it!=v[u].end(); it++) {
        dp(*it),f2=(f2*(f0[*it]+f1[*it])+f1[u]*f1[*it])%mod;
        f1[u]=(f0[u]*f1[*it]+f1[u]*f0[*it])%mod,f0[u]=f0[u]*f0[*it]%mod;
    }
    f0[u]=(f0[u]+f2)%mod,v[u].clear();
}
bool cmp(int x,int y) {
    return p[x]<p[y];
}
int main() {
    int x;
    scanf("%d",&n),n++;
    for(int i=2; i<=n; i++)scanf("%d",&x),addedge(x+1,i);
    dfs(1,0);
    for(int i=1; i<=mxd; i++) {
        sort(b[i].begin(),b[i].end(),cmp);
        iter it=b[i].begin();
        bj[*it]=1,st[top=1]=*(it++);
        for(; it!=b[i].end(); it++) {
            int la=lca(st[top],*it);
            while(top) {
                if(d[la]>=d[st[top-1]]) {
                    if(la!=st[top])v[la].push_back(st[top]),la!=st[top-1]?st[top]=la:top--;
                    break;
                }
                v[st[top-1]].push_back(st[top]),top--;
            }
            st[++top]=*it,bj[*it]=1;
        }
        while(--top)v[st[top]].push_back(st[top+1]);
        dp(st[1]),ans=(ans+f1[st[1]]*qpow(2,n-b[i].size()))%mod;
        it=b[i].begin();
        for(; it!=b[i].end(); it++)bj[*it]=0;
    }
    printf("%lld",ans);
    return 0;
}