题解 P5281 【[ZJOI2019]Minimax搜索】

· · 题解

直接求 w(S)=k 的方案数很困难，考虑放宽条件求 w(S)\leq k 的方案数，即计算修改代价不大于 k 的方案数。

设 u 的权值为 dp_u，根的权值为 dp_1=W。如果有 W\in S，则只需要花费 1 的代价将 W 权值修改掉。这种情况是平凡的，所以接下来默认 w\notin S。

在整棵树上，满足 dp_u=W 的所有节点 u 构成了一条从叶子到根的链。如果这根链上有任何一个节点的权值发生改变，那么根的权值也会发生改变。

考虑每个叶子 x 和 W 的 lca，如果 lca 的深度为奇数，那么只有当 x>W 的时候，W 的权值才可能因为 x 发生改变。换言之，如果 x\in S，则此时将 x 修改为 x>W 一定比 x<W 更优。

因此，如果当前代价为 k，则根据与 W 的 lca 的深度，可以贪心地直接确定每个节点的权值。

将链上的边断掉，可以对每个联通块求解有多少种方案会使得子树中存在的权值 W 在当前位置被替换掉。设 f_u 表示使得 dp_u<W 的方案数，cnt_u 表示以 u 为根的子联通块内的总方案数（即 2 的叶子个数次方）。链上只要有一个节点能替换掉 W 就是合法的，因此合法的方案数为总方案数减去所有不合法的方案数之积：

ans=sum-\prod_{dp_u=W}([dep_u\operatorname{mod} 2\equiv 1]f_u+[dep_u\operatorname{mod} 2\equiv 0](cnt_u-f_u))

计算 f_u 的时候，注意到不存在权值为 W 的叶子，因此使得 dp_u>W 的方案数可以简单表示为 cnt_u-f_u 。转移也可以写出来了：

f_u=\begin{cases}\prod_{v\in son_u} f_v&dep_u\equiv 1\pmod{2}\\ cnt_u-\prod_{v\in son_u} (cnt_v-f_v)&dep_u\equiv 0\pmod{2} \end{cases}

设 g_u=cnt-f_u 当 dep_u\equiv 1\pmod{2}，g_u=f_u 当 dep_u\equiv 0\pmod{2}，那么就有：

ans=sum-\prod_{dp_u=W}(cnt_u-g_u) g_u=cnt_u-\prod_{v\in son_u}g_v

至此，枚举最大代价的限制 k，可以 O(n) 地计算答案的数量。

注意到将 k 在 1\sim n 中枚举的时候，每个叶子的 f 最多发生 1 次改变，这启发我们动态维护 dp 的过程。

重链剖分之后，有：

g_u=cnt_u+(-\prod_{v\in light_u}g_v)g_{weight_u}

可以发现这是一个 a_i=b+ca_{i+1} 的形式，并且满足结合律，所以可以直接照搬动态 dp 的做法。

在每次跳轻边的时候，都需要一次求逆，因此哪怕你写了全局平衡二叉树，复杂度依旧会达到 O(nlog^2n)。

维护轻儿子的积时，因为可能出现乘 0，除 0 的情况，所以需要一个额外的数组来统计 0 的个数。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define lc ls[p]
#define rc rs[p]
#define I inline int
#define V inline void
#define ll long long int
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define REP(u) for(int i=h[u],v;v=e[i].t;i=e[i].n)if(v!=pre[u])
const int N=2e5+1,mod=998244353,INF=0x3f3f3f3f,sgn[2]={-1,1};
V cmin(int&x,int y){if(y-x>>31)x=y;}
V cmax(int&x,int y){if(x-y>>31)x=y;}
V check(int&x){x-=mod,x+=x>>31&mod;}
int sum[N],zero[N];
int n,m,L,R,W,tot,qwq,bas=1;
int h[N],dep[N],dp[N],ans[N],co[N];
int siz[N],wes[N],tmp[N],pre[N],cnt[N];
int ls[N],rs[N],fa[N],id[N],top[N],d[N];
struct node{
    int b,c;
    node(int x=0,int y=1){b=x,c=y;}
    node operator+(const node&u)const{
        return(node){int((1ll*c*u.b+b)%mod),int(1ll*c*u.c%mod)};
    }
}a[N],t[N];
struct edge{int t,n;}e[N<<1];
V add_edge(int x,int y){
    e[++tot]=(edge){y,h[x]},h[x]=tot,d[x]++;
    e[++tot]=(edge){x,h[y]},h[y]=tot,d[y]++;
}
I Pow(ll t,int x,ll s=1){for(;x;x>>=1,t=t*t%mod)if(x&1)s=s*t%mod;return s;}
V input(){
    scanf("%d%d%d",&n,&L,&R);int x,y;
    FOR(i,2,n)scanf("%d%d",&x,&y),add_edge(x,y);
}
I leaf(int u){return u>1&&d[u]==1;}
V dfs0(int u){
    dp[u]=(~dep[u]&1)*INF;
    REP(u)dep[v]=dep[u]+1,pre[v]=u,dfs0(v),(dep[u]&1?cmax:cmin)(dp[u],dp[v]);
    if(leaf(u))dp[u]=u;
}
V dfs1(int u){
    siz[u]=1,cnt[u]=1+leaf(u),check(bas<<=leaf(u));
    REP(u)if(dp[v]!=W){
        dep[v]=dep[u]+1,pre[v]=u,dfs1(v),siz[u]+=siz[v];
        if(cnt[u]=1ll*cnt[u]*cnt[v]%mod,siz[v]>siz[wes[u]])wes[u]=v;
    }
    REP(u)if(dp[v]==W)dfs1(v);
}
V upd(int p){t[p]=t[lc]+a[p]+t[rc];}
V add(int x,int w){
    if(w)sum[x]=1ll*sum[x]*w%mod,a[x].c=1ll*a[x].c*w%mod;
    else if(!zero[x]++)a[x].c=0;
}
V del(int x,int w){
    if(w=Pow(w,mod-2))sum[x]=1ll*sum[x]*w%mod,a[x].c=1ll*a[x].c*w%mod;
    else if(!--zero[x])a[x].c=sum[x];
}
V build(int&p,int L,int R){
    if(L>R)return;
    int sum=0,now=0,x;
    FOR(i,L,R)sum+=siz[tmp[i]];
    for(x=L,sum>>=1;(now+=siz[tmp[x]])<sum;x++);
    p=tmp[x],build(lc,L,x-1),build(rc,x+1,R),fa[lc]=fa[rc]=p;
}
V init(int p){if(p)init(lc),init(rc),upd(p);}
V dfs2(int u,int p){
    id[tmp[++tot]=u]=m,siz[u]-=siz[wes[u]],sum[u]=1,co[u]=p;
    if(wes[u])a[u]={cnt[u],sum[u]=mod-1},dfs2(wes[u],p),top[u]=top[wes[u]];
    else{
        if(leaf(u)&&(a[u]={(u<=W)+(u<W),0},dep[u]&1))a[u].b=cnt[u]-a[u].b;
        build(top[u],1,tot),tot=0;
    }
    REP(u)if(v!=wes[u]&&dp[v]!=W)dfs2(v,p),fa[top[v]]=u,init(top[v]),add(u,t[top[v]].b);
}
V build(int u){
    dfs2(m=u,sgn[dep[u]&1]),init(top[u]),add(0,(cnt[u]+mod-t[top[u]].b)%mod);
    REP(u)if(dp[v]==W)build(v);
}
V init(){dfs0(dep[1]=1),W=dp[1],dfs1(sum[0]=1),tot=0,build(m=1);}
V modify(int p){
    int x=id[p];
    del(0,cnt[x]+mod-t[top[x]].b);
    for(a[p]={1,0};p;p=fa[p]){
        if(p==top[p]&&fa[p])del(fa[p],t[p].b);
        upd(p);
        if(p==top[p]&&fa[p])add(fa[p],t[p].b);
    }
    add(0,cnt[x]+mod-t[top[x]].b);
}
V work(){
    FOR(i,1,n){
        check(ans[i]=bas+mod-a[0].c);
        if(W+i<=n&&leaf(W+i)&&co[W+i]<0)modify(W+i);
        if(W-i>=2&&leaf(W-i)&&co[W-i]>0)modify(W-i);
    }
    ans[0]=0,ans[n]=bas-1;
    ROF(i,n,1)check(ans[i]+=mod-ans[i-1]);
    FOR(i,L,R)cout<<ans[i]<<' ';
}
int main(){
    input();
    init();
    work();
    return 0;
}
```

起码 10 个月没写动态 dp 了，写了好久