题解：P7390 「EZEC-6」造树

· · 题解

思路

我们将当前的点划分为两个集合 S,T，S 内为目前总度数大于 1 的连通块，T 内为总度数为 1 的连通块。

每次连一条边等价于合并两个连通块，不难发现连通块 u,v 不可以合并仅当 |S|+|T|\ne 2 且 u,v\in T。

初始每个点都是独立的连通块，每次要么从 S 中选两个连通块合并，要么从 S 和 T 中各取一个连通块合并，重复 n-2 次后，就只剩下两个连通块且都属于 T，把它们合并就形成一棵树了。

由于题目保证一定有解，这么做一定是对的。考虑构造一个合并顺序，使得价值和最大。

这里定义一个连通块的权值为连通块内剩余度数不为 0 的点权最大值，说白了就是还可以往外连边的点的最大点权。

一个直接的做法就是，用两个堆维护 S 和 T 中权值最大的连通块 x,y 和 S 中权值次大的连通块 z，每次拿 x 与 y,z 中权值更大的合并，并更新连通块大小。如果 x 的总度数变为 1 了，则将其从 S 移到 T。重复操作，直至 S=\varnothing,|T|=2，将 T 中剩余元素合并，结束。

证明

对于链的情况，贪心显然成立，降序排序 b_i 后相邻合并即可得证。

对于非链情况，考虑交换论证，对于当前连通块 u\in S，由贪心规则可知，不存在 v\in S,b_u<b_v，且对于目前处理的点 u，本轮贪心连接的点集为 D_u，按照贪心规则，其必定连接 (S\cup T)-\{u\} 形成的集合中前 |D_u| 大的点，记这样的集合为 L。

如果存在一种策略不依赖于此限制且得到的答案最优，则必定存在一轮处理时，连通块 u 连接的点集 D_u\ne L，也就是存在 x\notin L ，且存在 y\in L 与 v\in (S-\{u\}) 连边。

可以通过调整使得该策略满足贪心规则，调整对答案产生的变化量为：

\Delta=(b_ub_y+b_vb_x)-(b_ub_x+b_vb_y)=(b_u-b_v)(b_y-b_x)

由于 b_u\ge b_v,b_y\ge b_x，因此 \Delta\ge 0，进行这样的调整是不劣的。

综上，贪心思路正确。

维护

直接拿堆维护是 O(n\log n) 的，会超时。考虑对每个点按 b_i 降序排序，然后大力上四个队列 q_1,q_2,q_3,q_4 维护：S 中权值最大的连通块、S 中的其他连通块、最开始 T 中的连通块、操作过程中从 S 移动到 T 的连通块。

初始 q_1 为 b_i 最大的非叶子节点，q_2 为其他非叶子节点，q_3 为所有叶子节点，q_4 为空。

由于 b_i 降序，初始化的队列中的元素也是降序的。于是就可以拿 q_2,q_3,q_4 中队首权值最大的点，与 q_1 的队首连边，然后将其从原队列中删除，加入 q_1，并更新连通块总度数。如果操作过程中 q_1 队首节点度数为 0 则直接删除，不参与后续操作。重复操作直至 q_1 中的连通块总度数为 1，此时 q_1 中仅有一个元素，其可代表整个连通块，将其移动到 q_4，然后将 q_2 队首加入 q_1，重复上述操作。当连了 n-2 条边时结束操作。

此时四个队列仅剩两个元素，且其剩余度数皆为 1，连边，计算答案，结束。

上述过程每个节点入队、出队次数为 O(1) 次，时间复杂度 O(n)。

瓶颈在排序，总复杂度 O(n\log n)，当然本题 b_i 的值域较小，把 sort 换桶排可以做到 O(n)。

代码

#include<bits/stdc++.h>
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
//#define int long long 
#define in(a) a = read()
#define PII pair<int , int>
using namespace std;
typedef long long ll;
const int N = 1e7 + 5 , mod = 998244353;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f; 
inline int read() {
    int x = 0;
    char ch = getchar();
    bool f = 0;
    while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();
    while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();
    return f ? -x : x;
}
int n;
struct node{
    int d , w;
}a[N];
bool cmp(node x , node y) {
    return x.w > y.w;
}
unsigned seed;
unsigned rnd(unsigned x){
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}
int rad(int x , int y){
    seed = rnd(seed);
    return seed % (y - x + 1) + x;
}
void init_data(){
    in(n) , in(seed);
    for(int i = 1 ; i <= n ; i ++) a[i].d = 1 , a[i].w = rad(1 , 500000);
    for(int i = 1 ; i <= n - 2 ; i ++) a[rad(1 , n)].d ++;
}
queue<int>q1 , q2 , q3 , q4;
signed main() {
    //cin_fast;
    int type;
    in(type);
    if(type) init_data();
    else {
        in(n);
        for(int i = 1 ; i <= n ; i ++) in(a[i].d);
        for(int i = 1 ; i <= n ; i ++) in(a[i].w);
    }
    sort(a + 1 , a + n + 1 , cmp);
    int k , s = n - 2 , tot;
    for(int i = 1 ; i <= n ; i ++) {
        if(a[i].d > 1) {
            q1.push(i) , k = i , tot = a[i].d;
            break;
        }
    }
    for(int i = 1 ; i <= n ; i ++) {
        if(a[i].d == 1) q3.push(i);
        else if(i != k) q2.push(i);
    }
    ll ans = 0;
    while(s) {
        while(!q1.empty() && tot > 1 && s) {
            int u = q1.front() , v = inf;
            if(!q3.empty()) v = q3.front();
            if(!q2.empty() && q2.front() < v) v = q2.front();
            if(!q4.empty() && q4.front() < v) v = q4.front();
            if(!q3.empty() && v == q3.front()) q3.pop();
            else if(!q2.empty() && v == q2.front()) q2.pop(); 
            else q4.pop();
            ans += (ll)a[u].w * a[v].w;
            a[u].d -- , a[v].d -- , tot -- , s --;
            if(a[u].d == 0) q1.pop();
            if(a[v].d > 0) q1.push(v) , tot += a[v].d;
        }
        if(!q1.empty()) q4.push(q1.front()) , q1.pop();
        if(!q2.empty()) tot = a[q2.front()].d , q1.push(q2.front()) , q2.pop();
    }
    while(!q4.empty()) q3.push(q4.front()) , q4.pop();
    while(!q2.empty()) q3.push(q2.front()) , q2.pop();
    int x = q3.front();
    q3.pop();
    int y = q3.front();
    cout << ans + (ll)a[x].w * a[y].w;
    return 0;
}
/*
我怀念过往的点点滴滴，正如这代码中的队列交替，不经意间我已到了队列的那头，腼腆地接过配对节点的双手。
*/