题解：P10226 [COCI 2023/2024 #3] Restorani

· · 题解

分析

把餐厅看成白点，冰淇淋店看成黑点。

对于一条边 (u,v)，记两侧黑点与白点数量差分别为 x,-x。那么这条边至少额外经过 2|x| 次。如果与 1 异侧的那边存在黑点或白点就需要和 2 取较大值。记这个为 s_{(u,v)}。

那么答案的下界就是 \sum\limits_{(u,v)\in E}^{} s_{(u,v)}。考虑构造这个下界。

对于每个点 u，维护访问顺序。

首先对 u 自己如果同时有 WB 就匹配掉。记 u 的所有儿子与自己一共多出来了 a 个 W 和 b 个 B。随便将 \min(a,b) 个 WB 匹配掉。这样显然能够保证 (u,fa_u) 这条边的额外经过次数为 |a-b|。而 a-b 恰好就是黑白点数量差。

用链表维护访问顺序就行了。对于多 B 的儿子，强制最后一个多出来的 B 后一个遍历点是第一个 W；对于多 W 的儿子，强制第一个多出来的 W 前一个遍历点是最后一个 B。

这样合并一个儿子 v 时：

  1. 如果它没有多出来 W 或 B，就直接把它的顺序 WBWB\dots 拼在 u 维护的答案顺序链表后面。
  2. 如果多出来 B，设多出来了 x 个 B。将顺序维护成 (BWBWB\dots WB)BB\dots。拼在 u 维护的多出来的 B 顺序链表后面。
  3. 如果多出来 W，同理。

最后将前 \min(a,b) 个 WB 匹配掉。每匹配一对就拼在 u 维护的答案顺序链表后面。最后如果多出来 B 或 W，再将链表维护成 (BWBWB\dots WB)BB\dots 或 (WBWB\dots WBW)WW 的形式。

整体复杂度 O(n+m)。

代码

const int N = 6e5 + 10;
int n, m;
int a[N], b[N], delt[2][N];
int id[2][N];
vector<int> e[N];
int spd;
int hd[3][N], tl[3][N], nxt[N], Nxt[N], Hd[N];

il void dfs(int u, int fa){
    if(a[u] && b[u]){
        hd[0][u] = id[0][u];
        nxt[id[0][u]] = id[1][u];
        tl[0][u] = id[1][u];
    }
    else if(a[u]){
        delt[0][u] = 1;
        hd[1][u] = id[0][u];
        tl[1][u] = id[0][u];
        Hd[id[0][u]] = id[0][u];
    }
    else if(b[u]){
        delt[1][u] = 1;
        hd[2][u] = id[1][u];
        tl[2][u] = id[1][u];
        Hd[id[1][u]] = id[1][u];
    }
    for(auto v: e[u]) if(v != fa){
        dfs(v, u);
        a[u] += a[v];
        b[u] += b[v];
        int vv = 2 * abs(a[v] - b[v]);
        if(a[v] || b[v]) vv = max(vv, 2ll);
        spd += vv;
        if(delt[0][v] == 0 && delt[1][v] == 0){
            if(hd[0][v]){
                if(!hd[0][u]) hd[0][u] = hd[0][v], tl[0][u] = tl[0][v];
                else nxt[tl[0][u]] = hd[0][v], tl[0][u] = tl[0][v];
            }
        }
        else if(delt[0][v]){
            if(!hd[1][u]) hd[1][u] = hd[1][v], tl[1][u] = tl[1][v];
            else Nxt[tl[1][u]] = hd[1][v], tl[1][u] = tl[1][v];
        }
        else{
            if(!hd[2][u]) hd[2][u] = hd[2][v], tl[2][u] = tl[2][v];
            else Nxt[tl[2][u]] = hd[2][v], tl[2][u] = tl[2][v];         
        }
        delt[0][u] += delt[0][v],
        delt[1][u] += delt[1][v];
    }
    int D = min(delt[0][u], delt[1][u]);
    delt[0][u] -= D,
    delt[1][u] -= D;
    while(D --){
        int x = hd[1][u], y = hd[2][u];
        hd[1][u] = Nxt[x], hd[2][u] = Nxt[y];
        if(!hd[0][u]) hd[0][u] = Hd[x];
        else nxt[tl[0][u]] = Hd[x];
        nxt[x] = Hd[y];
        tl[0][u] = y;
    }
    if(delt[0][u]){    
        int x = hd[1][u]; 
        if(hd[0][u]){
            nxt[tl[0][u]] = Hd[x];  
            Hd[x] = hd[0][u];
        }
        hd[0][u] = tl[0][u] = 0; 
    }
    else if(delt[1][u]){
        int x = hd[2][u];
        if(hd[0][u]){
            nxt[x] = hd[0][u];  
            int y = Nxt[x];
            Hd[tl[0][u]] = Hd[x]; 
            Nxt[tl[0][u]] = y;
            hd[2][u] = tl[0][u]; 
            if(tl[2][u] == x) tl[2][u] = tl[0][u];
        }
        hd[0][u] = tl[0][u] = 0;
    }
    return ;
}

il void solve(){ 
    n = rd, m = rd;
    U(i, 1, m){
        int x = rd;
        a[x] = 1;
        id[0][x] = i;
    }
    U(i, 1, m){
        int x = rd;
        b[x] = 1;
        id[1][x] = i + m;
    }
    UU(i, 1, n){
        int u = rd, v = rd;
        e[u].emplace_back(v),
        e[v].emplace_back(u);
    }
    dfs(1, 0);
    cout << spd << "\n";
    int u = hd[0][1], cnt =0 ;
    while(u) cout << (u > m ? u - m : u) << " ", u = nxt[u];
    // assert(cnt == 2 * m);
    return ;
}