洛谷题单指南-最小生成树-CF1120D Power Tree

原题链接：https://www.luogu.com.cn/problem/CF1120D

题意解读：在一颗树中，每个节点u都可以对其子树所有叶子节点增加一个数x(x可以是正、负、0)，每个节点i的操作都有代价c[u]，假定叶子节点初始设置为任意值，求选择哪些节点做操作，可以使得叶子节点值都变成0，且总的代价之和最小，并输出具体方案涉及的节点集合，对于都满足最小代码的方案节点取并集。

解题思路：问题非常抽象，即使理解了题意，直接从树上考虑也没有更好的方案，必须进行问题转化。

1、问题分析

由于操作涉及节点子树的所有叶子节点，非单点操作，可以看看能不能转换成区间问题？

我们知道，在对树DFS的过程中，每个节点会产生一个DFS序，而一个节点的子树中所有的叶子节点的DFN一定是递增的。

当我们将所有叶子节点按DFS顺序进行编号，会形成1~k的编号，一个节点的子树叶子节点的编号在1~k中一定是连续的（不难画图验证）。

因此，对一个节点i的操作，意味着对其子树叶子节点范围[l,r]进行增加值，这样一个操作的代价就是c[i]。

问题要求的就是所有操作中，选一些代价和最小的，能确保让每个有任意初始值的叶子节点的值都变成0。

2、问题转化

设树中叶子节点有k个，对于树中的每个节点，都可以在DFS过程中计算出其子树叶子节点在dfs顺序中的最小、最大编号，这样就得到了若干个

操作，每个操作e[i]都有以下信息：

struct Edge
{
  int l; //操作涉及叶子节点区间的最小值
  int r; //操作涉及叶子节点区间的最大值
  int w; //操作的代价，c[id]
  int id; //对应原树中节点编号
} e[N];

现在，问题就转化成了上面分析中的模型，接下来看这个问题如何求解。

问题建模：一个序列a[1]~a[k]（对应所有叶子节点的值），给出n个区间操作{l,r,w,id}，每个操作可以将a[l]~a[r]每个数加上一个数x，每个操作也有一个代价w，要挑选出代价和最小的区间操作，使得a[1]~a[n]都变成0，并记录所有可能在最优方案中的区间操作编号id的并集。

3、算法思路

对区间a[l,r]每个数增加一个数x，从差分的角度来看，设差分数组为b，就是对b[l] += x，b[r+1] -=x。

要让a[1]~a[n]全部通过操作变为0，意味着要不断对差分数组做b[l] += x，b[r+1] -=x，让b[1]~b[n]都变为0，所有的值都会累加到b[n+1]。

如差分数组b：1 2 3 0，要让b[1]~b[3]为0，一组可能的操作如下（假设第一个数下标是1）：

b[1] += -1, b[4] += 1，b变成：0 2 3 1

b[2] += -2,b[4] += 2，b变成：0 0 3 3

b[3] += -3,b[4] += 3，b变成：0 0 0 6

可以看出，b[1] ~ b[3]的值都累加到b[4]了。

以上操作都是基于每个元素以及最后一个元素来做，具体对哪些区间操作，要看有哪些区间可以选择，但不管选择哪些区间，最终一定要能够

传导到最后一个元素，比如：

先对b[1] += -1, b[2] += 1，这是b变成：0 3 3 0

在将后面的值变成的0过程，还会把值往后传递，直到所有值都为0，最后一个元素累计的前面所有元素的和。

如果用图论的思想，有n个操作{l,r,w,id}，要选择最少代价的操作将差分数组b每一项都变成0，以为这选择的操作需要覆盖所有叶子结点的编号1~k，并且还要覆盖到k+1。

因此，可以对每个操作的l - r + 1建立一条权值为w的边，同时记录id，然后针对这个图跑最小生成树kruskal算法，最小生成树的权值和就是最小代价。

另外，本题要输出所有可能是最优解的id集合，那么在kruskal过程中，要针对w相同的一批边进行处理，如果这些边都能带来集合的连通，那么这些边对应的id值都应该加入答案，具体可以参考代码。
100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

vector<int> g[N]; //初始树邻接表
struct Edge
{
    int l, r, w, id;
    bool operator < (const Edge &edge) const
    {
        return w < edge.w;
    }
} e[N]; //每个节点操作对应的子树叶子结点区间、操作代价、节点编号
int cnt; //e的size
int p[N]; //并查集
int c[N]; //每个节点的操作代价
int sl[N], sr[N]; //sl[i]、sr[i]是i节点子树叶子的最小dfs序、最大dfs序
int idx; //叶子节点的dfs序编号
long long ans1;
vector<int> ans2;
int n;

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

//遍历每一个节点，构建每个节点能对其子树叶子节点操作的信息
void dfs(int u, int p)
{
    sl[u] = 1e9, sr[u] = 0;
    bool leaf = true; //u是叶子节点
    for(auto v : g[u])
    {
        if(v == p) continue;
        leaf = false; //有子节点说明u不是叶子节点
        dfs(v, u);
        sl[u] = min(sl[u], sl[v]); //u的子树叶子最小序号是每一个v子树叶子最小序号
        sr[u] = max(sr[u], sr[v]); //u的子树叶子最大序号是每一个v子树叶子最大序号
    }
    //u是叶子节点
    if(leaf)
    {
        sl[u] = sr[u] = ++idx;
    }
    //针对u可以构建一个操作，加入边集数组
    cnt++;
    e[cnt].l = sl[u];
    e[cnt].r = sr[u] + 1;
    e[cnt].w = c[u];
    e[cnt].id = u;
}

void kruskal()
{
    sort(e + 1, e + cnt + 1);
    for(int i = 1; i <= cnt; i++) p[i] = i;

    for(int i = 1; i <= cnt; i++)
    {
        //先找到连续w大小一样的边，如果可以造成连通，则都加入答案
        int j = i; 
        while(j < cnt && e[j + 1].w == e[j].w) j++;

        for(int k = i; k <= j; k++)
        {
            int a = find(e[k].l);
            int b = find(e[k].r);

            if(a != b) //能导致连通
            {
                ans2.push_back(e[k].id);
            }
        }

        //再实际进行连通处理
        for(int k = i; k <= j; k++)
        {
            int a = find(e[k].l);
            int b = find(e[k].r);
            if(a != b) 
            {
                p[a] = b;
                ans1 += e[k].w;
            }
        }

        i = j;
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> c[i];
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0); //通过dfs构建边集数组e
    kruskal();
    sort(ans2.begin(), ans2.end());
    cout << ans1 << " " << ans2.size() << endl;
    for(auto item : ans2) cout << item << " ";
}