题解 CF671D 【Roads in Yusland】

xht · 2020-03-01 01:04:15 · 题解

CF671D Roads in Yusland

题意

• 给定一棵 n 个点的以 1 为根的树。
• 有 m 条路径 (x,y)，保证 y 是 x 的祖先，每条路径有一个权值。
• 你要在这些路径中选择若干条路径，使它们能覆盖每条边，同时权值和最小。

题解

设 f_i 表示覆盖 i 子树内的所有边和 i 与其父亲的边的最小权值，则答案就是 \sum_{x \in \operatorname{son}(1)} f_x。

然而并不是所有 f 都是最优的，对于一种覆盖 i 子树内的所有边和 i 与其父亲的边的方案，可能它并不是最小权值，但是它向上延伸得更长。

因此我们要保留住所有可能最优的方案，同时要计算其中的最小值，这启发我们考虑小根堆。具体来说，对于节点 i，i 上的小根堆内存储了覆盖 i 子树内的所有边和 i 与其父亲的边的所有可能最优的方案。

考虑如何转移，即当 x \in \operatorname{son}(y) 时，如何将 x 上的方案转移到 y 上。对于一个权值为 k 的方案：

• 如果向上延伸超过了 y，则这种方案在 y 的小根堆里权值应该为 k + \sum_{z \in \operatorname{son}(y)} f_z - f_x。
• 如果正好向上延伸到 y，则这种方案不应该出现在 y 上，需要被扔掉。

这时候我们发现，一个点有来自多个儿子的小根堆，显然我们需要将它们合并起来，于是将小根堆改为左偏树即可。

同时，我们还需要支持整棵左偏树加上一个定值，打个标记即可。

对于需要扔掉的方案，由于我们不需要实时删除，因此考虑我们暂时先保留它们，当它们成为根时再弹出即可。

设 n,m 同阶，总时间复杂度为 \mathcal O(n \log n)。

代码

#define Fail print(-1), exit(0)
const int N = 3e5 + 7;
int n, m, d[N], tot, rt[N];
ll f[N], ans;
vi e[N];
vector<pi> p[N];
struct T {
    pair<ll, int> x;
    ll z;
    int l, r, f, d;
} t[N];

inline void add(int x, ll k) {
    if (x) t[x].x.fi += k, t[x].z += k;
}

inline void spd(int x) {
    if (t[x].z) add(t[x].l, t[x].z), add(t[x].r, t[x].z), t[x].z = 0;
}

int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (t[x].x > t[y].x) swap(x, y);
    spd(x);
    t[t[x].r=merge(t[x].r,y)].f = x;
    if (t[t[x].r].d > t[t[x].l].d) swap(t[x].l, t[x].r);
    t[x].d = t[t[x].r].d + 1;
    return x;
}

void dfs(int x, int fa) {
    d[x] = d[fa] + 1;
    for (pi o : p[x])
        t[++tot].x = o, t[tot].d = 1, rt[x] = merge(rt[x], tot);
    ll s = 0;
    for (int y : e[x])
        if (y != fa) {
            dfs(y, x), s += f[y];
            add(rt[y], -f[y]), rt[x] = merge(rt[x], rt[y]);
        }
    add(rt[x], s);
    while (rt[x] && d[t[rt[x]].x.se] >= d[x])
        spd(rt[x]), rt[x] = merge(t[rt[x]].l, t[rt[x]].r);
    if (!rt[x]) Fail;
    f[x] = t[rt[x]].x.fi;
}

int main() {
    rd(n), rd(m);
    for (int i = 1, x, y; i < n; i++)
        rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    for (int i = 1, x, y, z; i <= m; i++)
        rd(x), rd(y), rd(z), p[x].pb(mp(z, y));
    d[1] = 1;
    for (int x : e[1]) dfs(x, 1), ans += f[x];
    print(ans);
    return 0;
}