CF1120D 题解

· · 题解

前言

题目传送门！

更好的阅读体验？

这是一道巧妙的问题。前置芝士：dfs 序、最小生成树（kruskal）。

另外的题解讲得都很不详细，我就补篇题解。

思路

我们可以先找出这棵树的 dfs 序。dfs 序的特点是，相邻叶节点的 dfs 序总是连续的。

那对于每个点，我们就可以求出，它所能控制的叶节点对应的 dfn 序的一个区间。

这样就转化为一个区间问题了：

给定若干段区间 [l, r]，每个区间有一个代价 a_i（对应原图的点权）。

还有一段 [1, n] 的序列 a。

控制一个区间，表示可以对区间里的数任意加减。

求出最少代价以及方案，不管 a_i 是多少，总能将 a 的所有数变为 0。

区间多次修改，单次查询，很容易想到差分。

每次相当于在差分数组 c 上执行：c_l 加 x，c_{r + 1} 减 x。

并且显然有 1 \le l, r \le n，2 \le r + 1 \le n + 1（因为 l 和 r 是 dfs 序）。

换句话说，我们所能更改的数是 c_1 到 c_{n + 1}，要想让所有 c_i（1 \le i \le n）为 0，则所有数都要移到 c_{n + 1} 头上。

那么接下来就非常简单了：[l, r] 对应着一条 l \to r + 1 的边，边权为 a_i。求出最少边权和及方案，使得选择了这些边后，(n + 1) 号点能与所有点连通。

然后跑一遍 kruskal 即可。事实上转化为区间这一步只是推导过程，实际代码只需要在求出区间 [l, r] 时，直接连边即可。

在输出方案的时候注意：这里的方案是并集！也就是全部可能存在于最优方案的点。

这一点具体看代码。很容易理解。

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define space putchar(' ')
#define endl putchar('\n')
using namespace std;
typedef long long LL;
typedef long double LD;
void fastio()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
}
int read()
{
    char op = getchar(); int x = 0, f = 1;
    while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();}
    while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar();
    return x * f;
}
void write(LL x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
const int N = 2e5 + 5;
int n, m, a[N];
struct zltAK
{
    int u, v, w, pos; //a[pos] = w
}e[N];
void zltakioi(int u, int v, int pos)
{
    e[++m].u = u, e[m].v = v;
    e[m].w = a[pos], e[m].pos = pos;
}
bool cmp(zltAK IOI, zltAK CTSC) {return IOI.w < CTSC.w;} //膜拜 @zlttql 
int fa[N]; //并查集 
void init() {for (int i = 1; i <= n+1; i++) fa[i] = i;}
int get(int x)
{
    if (fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}
struct Edge
{
    int now, nxt, w;
}edge[N << 1];
int head[N], cur;
void add(int u, int v)
{
    edge[++cur].now = v;
    edge[cur].nxt = head[u];
    head[u] = cur;
}
//dfnl[i] 和 dfnr[i] 表示叶节点 dfn 序，如果控制 i，可以更改 dfnl[i]~dfnr[i] 的全部对应叶节点。 
int dfnl[N], dfnr[N];
void dfs(int u, int fa)
{
    bool leaf = true;
    dfnl[u] = 2147483647;
    for (int i = head[u]; i; i = edge[i].nxt)
    {
        int v = edge[i].now;
        if (v == fa) continue;
        leaf = false, dfs(v, u);
        dfnl[u] = min(dfnl[u], dfnl[v]), dfnr[u] = max(dfnr[u], dfnr[v]);
    }
    if (leaf) dfnl[u] = dfnr[u] = ++cur;
    zltakioi(dfnl[u], dfnr[u] + 1, u); //建边，差分思想如上所述 
}
int tot;
bool ans[N];
LL kruskal()
{
    init(), sort(e+1, e+m+1, cmp);
    LL sum = 0;
    for (int l = 1; l <= n;)
    {
        int r;
        for (r = l; r + 1 <= n && e[r].w == e[r+1].w; r++); //这样 [l,r] 的 w 都是一样的

        for (int i = l; i <= r; i++) //记录答案并集，注意不能一边合并一边统计，显然会错误 
            if (get(e[i].u) != get(e[i].v))
                ans[e[i].pos] = true, tot++;

        for (int i = l; i <= r; i++) //真正的kruskal操作 
        {
            int fu = get(e[i].u), fv = get(e[i].v);
            if (fu == fv) continue;
            fa[fu] = fv, sum += e[i].w;
        }
        l = r + 1;
    }
    return sum;
}
int main()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        add(u, v), add(v, u);
    }
    cur = 0, dfs(1, 0);
    write(kruskal()), space, write(tot), endl;
    for (int i = 1; i <= n; i++)
        if (ans[i])
            write(i), space;
    return 0;
}

希望能帮助到大家！