P11111 题解

· · 题解

Problem Link

题目大意

给定 n 个点的树，每个点点权 a_i 有一个限定范围 [l_i,r_i]，q 组询问给定 v，要求构造一组 a_i 使得树上最大权独立集为 v。

数据范围：n,q\le 2\times 10^5。

思路分析

考虑所有 a_i=l_i 和所有 a_i=r_i 时的最大权独立集 v_L,v_R，容易发现 v<v_L 或 v>v_R 一定无解。

然后考虑每次令某个 a_u\gets a_u+1，容易发现此时最大权独立集大小增量 \in\{0,1\}。

那么 v\in[v_L,v_R] 时一定有解，我们可以对每个 a_i 依次从 l_i 增加到 r_i。

容易发现一定存在某个时刻 x 使得 a_i\ge x 后每次增加 a_i，最大独立集的大小也增加，即增加 a_i 会导致最大独立集增加的时刻是一段后缀。

那么我们求出 a_{1\sim i} 变成 r_x，a_{i+1\sim n} 为 l_x 时的最大权独立集 v_i，找到第一个 v_i>v，那么 a_{1\sim i-1} 为 r_x，a_{i+1\sim n} 为 l_x，a_i=r_i-(v_i-v) 即为一组解。

如果按 1\sim n 的顺序逐个修改，需要用全局平衡二叉树维护 ddp，但是如果按 dfn 序修改，可以简单换根 dp 求出。

时间复杂度 \mathcal O(n+q\log n)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,q,dcnt;
vector <int> G[MAXN];
ll X,Y,M;
ll l[MAXN],r[MAXN],s[MAXN],hv[MAXN],rk[MAXN],p[MAXN],t[MAXN];
array<ll,2> f[MAXN],g[MAXN];
ll hsh(int i,ll z) { return (i*X+z*z%M*Y)%M; }
void dfs1(int u,int fz) {
    f[u]={0,l[u]},g[u]={0,r[u]};
    for(int v:G[u]) if(v^fz) {
        dfs1(v,u);
        f[u][0]+=max(f[v][0],f[v][1]);
        g[u][0]+=max(g[v][0],g[v][1]);
        f[u][1]+=f[v][0];
        g[u][1]+=g[v][0];
    }
}
void dfs2(int u,int fz,array<ll,2>o) {
    rk[++dcnt]=u,hv[dcnt]=hv[dcnt-1]^hsh(u,l[u])^hsh(u,r[u]);
    o[0]+=f[u][0],o[1]+=f[u][1]+r[u]-l[u],s[dcnt]=max(o[0],o[1]);
    for(int v:G[u]) if(v^fz) {
        o[0]-=max(f[v][0],f[v][1]),o[1]-=f[v][0];
        dfs2(v,u,{max(o[0],o[1]),o[0]});
        o[0]+=max(g[v][0],g[v][1]),o[1]+=g[v][0];
    }
}
void solve() {
    scanf("%d%d%lld%lld%lld",&n,&q,&X,&Y,&M);
    for(int i=1;i<=n;++i) G[i].clear();
    for(int i=1,u,v;i<n;++i) {
        scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    }
    for(int i=1;i<=n;++i) scanf("%lld%lld",&l[i],&r[i]);
    dfs1(1,0);
    s[0]=max(f[1][0],f[1][1]),hv[0]=0;
    for(int i=1;i<=n;++i) hv[0]^=hsh(i,l[i]);
    dcnt=0,dfs2(1,0,{0,0});
    for(int i=1;i<=q;++i) scanf("%lld",&p[i]);
    for(int i=1;i<=q;++i) {
        if(p[i]<s[0]||p[i]>s[n]) printf("-1 ");
        else {
            int j=lower_bound(s,s+n+1,p[i])-s,u=rk[j];
            ll k=s[j]-p[i],ans=hv[j]^hsh(u,r[u])^hsh(u,r[u]-k);
            printf("%lld ",ans);
        }
    }
    puts(""),fflush(stdout);
    while(true) {
        int o; scanf("%d",&o);
        if(!o) break;
        if(p[o]<s[0]||p[o]>s[n]) puts("-1");
        else {
            int j=lower_bound(s,s+n+1,p[o])-s,u=rk[j];
            for(int i=1;i<=j;++i) t[rk[i]]=r[rk[i]];
            for(int i=j+1;i<=n;++i) t[rk[i]]=l[rk[i]];
            t[u]-=s[j]-p[o];
            for(int i=1;i<=n;++i) printf("%lld ",t[i]);
            puts("");
        }
        fflush(stdout);
    }
}
signed main() {
    int T; scanf("%d",&T);
    while(T--) solve();
    return 0;
}