题解：P11091 [ROI 2021] 工作报告 (Day 1)

EzSun · 2026-11-10 12:51:32 · 题解

好题。

对于每一个父节点都要为其子节点钦定一个顺序使得相邻子节点的区间不相交且单调上升。K \leq 8 让我们很容易想到用状压去处理这个过程。但怎么得到子节点所有可行的区间呢？

直接存储即可，下面给出证明有用的总区间个数是 O(n \log n) 级别的。

发现对于一个节点，如果存在两个可行区间是包含的关系，那么外层的区间一定是不优的，证明显然，我们就可以利用单调栈去去除这种区间。

那么对于剩下的区间，一个值至多在所有区间的左右端点各出现一次。设节点 u 的可行区间数为 s_u，那么有

那么就是一个类似于树上启发式合并的过程，时间复杂度显然是 O(n \log n) 的。

注意对于单儿子节点要复用信息而非复制，否则上面的证明不成立，空间复杂度会退化为 O(n^2)。

Code

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int N = 1e5 + 7, K = 8, inf = 0x3f3f3f3f;
int Case, Task;
int n;
vector<pii>f[N];
vector<vector<pii> >order[N];
vector<int>ans[N];
int g[1 << K];
pii lst[1 << K];
int rt[N];
bool leaf[N];
struct Node{
    int l, r;
    vector<pii>od;
};
bool cmp1(Node &a, Node &b){
    return a.l < b.l;
}
struct Edge{
    vector<int>e[N];
    void add(int x, int y){
        e[x].push_back(y);
    }
    void dfs1(int u){
        rt[u] = u;
        vector<Node>vec;
        for(int v : e[u]){
            dfs1(v);
        }
        int num = e[u].size();
        if(num == 1){
            rt[u] = rt[e[u][0]];
            return;
        } 
        int U = (1 << num);
        for(int i = 0; i < num; i++){
            int st = rt[e[u][i]];   
            for(int ii = 0; ii < f[st].size(); ii++){
                auto tmp = f[st][ii];
                memset(g, 0x3f, sizeof(g));
                g[1 << i] = tmp.second;
                lst[1 << i] = make_pair(i, ii);
                for(int S = 0; S < U; S++){
                    if(g[S] == inf) continue;
                    for(int j = 0; j < num; j++){
                        if(S & (1 << j)) continue;
                        int v = rt[e[u][j]];
                        auto it = lower_bound(f[v].begin(), f[v].end(), make_pair(g[S], g[S]));
                        if(it != f[v].end()){
                            if(it -> second < g[S | (1 << j)]){
                                g[S | (1 << j)] = it -> second;
                                lst[S | (1 << j)] = make_pair(j, it - f[v].begin());
                            }
                        }
                    }
                }
                if(g[U - 1] != inf){
                    vector<pii>od;
                    for(int S = U - 1; S; S ^= (1 << lst[S].first)){
                        od.push_back(lst[S]);
                    }
                    reverse(od.begin(), od.end());
                    vec.push_back({tmp.first, g[U - 1], od});
                }
            }
        }
        sort(vec.begin(), vec.end(), cmp1);
        for(auto tmp : vec){
            while(!f[u].empty() && tmp.r < f[u].back().second) f[u].pop_back(), order[u].pop_back();
            f[u].push_back(make_pair(tmp.l, tmp.r));
            order[u].push_back(tmp.od);
        }
    }
    void dfs2(int u, int x){
        if(leaf[u]){
            ans[u].push_back(f[u][x].first);
            return;
        }
        for(auto it : order[u][x]){
            int v = it.first, y = it.second;
            v = e[u][v];
            ans[u].push_back(v);
            v = rt[v];
            dfs2(v, y);
        }
    }
}E;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1, op, ki; i <= n; i++){
        cin >> op;
        if(op == 1){
            cin >> ki;
            while(ki--){
                int v;
                cin >> v;
                E.add(i, v);
            }   
        }
        else{
            cin >> ki;
            leaf[i] = 1; 
            while(ki--){
                int x;
                cin >> x;
                f[i].push_back(make_pair(x, x));
            }
            sort(f[i].begin(), f[i].end());
        }
    }
    E.dfs1(1);
    if(f[rt[1]].size() == 0){
        printf("No\n");
    }
    else{
        printf("Yes\n");
        E.dfs2(rt[1], 0);
        for(int i = 1; i <= n; i++){
            if(rt[i] != i){
                printf("%d\n", E.e[i][0]);
                continue;
            }
            for(int u : ans[i]){
                printf("%d ", u);
            }
            puts("");
        }
    }
    return 0;   
}