【CF617D】Roads in Yusland

题面

蒯的洛谷的

题解

我们现在已经转化好了题目了，戳这里

那么我们考虑怎么求这个东西，我们先判断一下是否所有的边都能被覆盖，不行的话输出\(-1\)。

再将路径\(u\rightarrow v(dep_u>dep_v)\)以其权值为关键字丢到以\(u\)为根的左偏树(小根)上，

再进行\(dfs\)，合并\(x\)的所有儿子的左偏树，对于点\(x\)，我们能选则选，

还有打标记等细节，详见代码。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

namespace IO {

    const int BUFSIZE = 1 << 20;

    char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;

    inline char gc() {

        if (is == it) it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);

        return *is++;

    }

}

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (ch != '-' && (ch > '9' || ch < '0')) ch = IO::gc();

    if (ch == '-') w = -1 , ch = IO::gc();

    while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = IO::gc();

    return w * data;

}

const int MAX_N = 3e5 + 5;

struct Graph { int to, next; } e[MAX_N << 1];

int fir[MAX_N], e_cnt;

void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; }

void Add_Edge(int u, int v) { e[e_cnt] = (Graph){v, fir[u]}; fir[u] = e_cnt++; }

struct chain { int u, v, w; } a[MAX_N];

int N, M, c[MAX_N], dep[MAX_N];

long long ans = 0;

void dfs(int x, int f) {

    dep[x] = dep[f] + 1;

    for (int i = fir[x]; ~i; i = e[i].next) {

        int v = e[i].to; if (v == f) continue;

        dfs(v, x), c[x] += c[v];

    }

}

struct Node {

    int ls, rs, dis;

    int v, ed, tag;

} t[MAX_N];

int rt[MAX_N];

void puttag(int x, int v) { t[x].tag += v, t[x].v += v; }

void pushdown(int x) {

    if (!t[x].tag) return ;

    if (t[x].ls) puttag(t[x].ls, t[x].tag);

    if (t[x].rs) puttag(t[x].rs, t[x].tag);

    t[x].tag = 0;

}

int merge(int x, int y) {

    if (!x || !y) return x + y;

    pushdown(x), pushdown(y);

    if (t[x].v > t[y].v) swap(x, y);

    t[x].rs = merge(t[x].rs, y);

    if (t[t[x].ls].dis < t[t[x].rs].dis) swap(t[x].ls, t[x].rs);

    t[x].dis = t[t[x].rs].dis + 1;

    return x;

}

void solve(int x, int f) {

    for (int i = fir[x]; ~i; i = e[i].next)

        if (e[i].to != f) {

            solve(e[i].to, x);

            rt[x] = merge(rt[e[i].to], rt[x]);

        }

    if (x == 1) return ;

    while (dep[t[rt[x]].ed] >= dep[x]) rt[x] = merge(t[rt[x]].ls, t[rt[x]].rs);

    int w = t[rt[x]].v;

    ans += w, puttag(rt[x], -w);

}

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

    clearGraph();

    N = gi(), M = gi();

    for (int i = 1; i < N; i++) {

        int u = gi(), v = gi();

        Add_Edge(u, v), Add_Edge(v, u);

    }

    for (int i = 1; i <= M; i++) a[i] = (chain){gi(), gi(), gi()};

    for (int i = 1; i <= M; i++) c[a[i].u]++, c[a[i].v]--;

    dfs(1, 0);

    for (int i = 2; i <= N; i++) if (c[i] <= 0) return puts("-1") & 0;

    for (int i = 1; i <= M; i++) t[i] = (Node){0, 0, 0, a[i].w, a[i].v, 0}, rt[a[i].u] = merge(rt[a[i].u], i);

    solve(1, 0);

    cout << ans << endl;

    return 0;

}

跑到洛谷\(rank1\)纪念一下：

好像还是cf的\(rank1\)呢qaq：