题解 P6061 【最优性剪枝 search】

Zory · 2020-02-04 12:04:55 · 题解

虽然我没有出题水平，不过感觉这题质量和难度一般般，可能是时间的缘故较少人过

官方题解中提到可以用树状数组写，给大家一份代码，因为没细看官方题解不知道其他思路是否一致

首先显然将答案写成 \sum_x x 被访问到的概率，这个是基本的期望线性性，然后这里x被访问到的条件为没有访问过dep更小的点

于是容易得到一个复杂度不重要的暴力：

vc<int> son[N];int ff[N],val[N],dep[N];
void pre(int x){ dep[x]=dep[ff[x]]+1;val[x]=(!sz(son[x])?dep[x]:INF);for(auto y:son[x]) pre(y),chmin(val[x],val[y]); }
void main()
{
    int n=qread();fo(i,2,n) son[ff[i]=qread()].PB(i);pre(1);
    fo(x,1,n) sort(all(son[x]),[&](int x,int y){return val[x]<val[y];});
    ll ans=0;
    fo(x,1,n)
    {
        ll now=1;
        for(int anc=ff[x],lst=x;anc;lst=anc,anc=ff[anc])
        {
            int cnt=0;for(auto y:son[anc]) if(y!=lst and val[y]<dep[x]) cnt++;
            now=now*invm(cnt+1)%MOD;
        }add(ans,now);
    }write(ans);
}

容易发现很明显每个点的权值应该是容易维护的。具体的，将孩子排序，从孩子i切换到孩子i+1时，变化的只有[val_i,val_{i+1})=\frac{1}{i} \to \frac{1}{i+1}，于是用个树状数组维护乘法差分即可，O(nlogn)

namespace BIT
{
    ll bit[N];void clear(){ fo(i,1,N-1) bit[i]=1; }
    int lowbit(int x){return x&-x;}
    void mul(int x,ll c){ while(x<N) bit[x]=bit[x]*c%MOD,x+=lowbit(x); }
    void MUL(int l,int r,ll c){ mul(l,c),mul(r,invm(c)); }//[l,r)*=c
    ll ask(int x){ ll ret=1;while(x>=1) ret=ret*bit[x]%MOD,x-=lowbit(x);return ret; }
};
ll ans=0;
void solve(int x)
{
    add(ans, BIT::ask(dep[x]-1) );
    int m=sz(son[x]);
    #define V(i) (i>m?N:val[son[x][i-1]])
    fo(i,2,m) BIT::MUL(V(i),V(i+1),invm(i));
    fo(i,1,m)
    {
        int y=son[x][i-1];solve(y);
        if(i<m) BIT::MUL(V(i),V(i+1),i*invm(i+1)%MOD);
    }
    fo(i,1,m-2) BIT::MUL(V(i),V(i+1),i+1);if(m>1) BIT::MUL(V(m-1),N,m);
}