题解：P11195 [COTS 2021] 疫苗接种 Cijepise

· · 题解

莫名其妙的题。

分析

首先这题不需要求没有修改时 u 变成根的时间。要求的话大概是发现对于 u 变到 fa_u 所需的时间是它其它兄弟节点为根的子树中前缀最小值不小于 val_u 的链的数量，然后处理一下。

但是这题需要我们让 u 变到根的时间最短，那么这个时间一定是 dep_u。因为我们存在答案上界是将 P(1,u) 全部修改成 inf，此时在 u 变成根以前是不会选择其它节点的。模拟一下发现可能会影响到 u 变成根的时间的点只会是 u 到 1 路径上所有点 x_i 的兄弟节点。只要存在一种修改方式，使得路径任意一个前缀，都满足 val_{x_i}> mx_{x_i} 就行了。其中 mx_{x_i} 是 x_i 到 1 路径上所有点的兄弟节点中最大的价值。

定义状态函数 f_u 表示让 u 满足条件的最小代价。那么一定有 f_v \in \{f_u,f_{u}+1\}[v\in son_u]。那么对于 v 来说，f_v=f_u+1 一定是当前前缀路径上存在至少一个点 x 的兄弟节点 y，满足 val_y \ge val_v。则对于 v 来说，我们可以选择将 val_v 变成 inf，对于 v 的子树来说，可以选择将 val_v 变成 inf 或将 val_y 变成 0。

如果 val_y\ge val_v 的数量为 1。则可看作将 val_v 变成 inf 或将 val_y 变成 0，此时将 val_y 变成 0 更优。

如果 val_y \ge val_v 的数量大于 1。若 v 子树点的最优策略均为 val_w 变成 inf，则变不变 val_y 无所谓。若存在 w 的最优策略为删点，当 val_w \le val_v 时，删的点要么是 y 中的一个，要么是 w 到 v 路径上点的兄弟节点中的一个，后者和 v 无关。当 val_v < val_w 时，如果将 val_y 变成 0，且满足 val_y \ge val_w，此时不劣。如果变成 0 的点满足 val_y < val_w，那么支持 w 的前提是将 val_v 变成 inf，此时 y 的变化可以看作将 val_v 变成 inf，无影响。

把上面的情况取交集，发现我们可以改变第一个满足 val_y \ge val_v 的点。

那么现在需要实现：快速加点或删点，快速查询第一个比 x 大的数的值，快速查询比 x 大的数的数量。可以任意维护，时间复杂度 O(n\log n+q)。

我说的是不是莫名奇妙的。

代码

const int N=1e6+10;
int n,q;
int val[N],f[N];
vector<int> e[N];
multiset<int> st;

il void dfs(int u,int fa){
    for(auto v:e[u])
    if(v!=fa) st.insert(val[v]);
    for(auto v:e[u])
    if(v!=fa){
        st.erase(st.find(val[v]));
        auto it=st.lower_bound(val[v]);
        int x=(it==st.end()?-1:(*it));
        if(it!=st.end()) f[v]=f[u]+1,st.erase(st.find(x));
        else f[v]=f[u];
        dfs(v,u);
        if(~x) st.insert(x); 
        st.insert(val[v]);
    }
    for(auto v:e[u])
    if(v!=fa) st.erase(st.find(val[v]));    
}

il void solve(){
    n=rd;
    for(re int i=1;i<=n;++i) val[i]=rd;
    for(re int i=1;i< n;++i){
        int u=rd,v=rd;
        e[u].push_back(v),
        e[v].push_back(u);
    }
    dfs(1,0);
    q=rd;
    while(q--) cout<<f[rd]<<"\n";
    return ;
}