B题

知识点:最大权闭合子图(网络流)+ 树链剖分、线段树优化建图
感觉只要学一下最大权闭合子图是啥,会线段树优化就能会做了...
只是代码又长又臭,写晕了。还有网络流dinic一定要当前弧优化,不然tle....

闭合子图:原图中选一个点集,点集中所有点和它们的出边构成新图,称为闭合子图。(选一个点就必须选它的后继点)

最大权闭合子图求法:
源点和所有正权点连边,流量为这个正权;所有负权点和汇点连边,流量为负权的相反数;原图的边(u,v)uv连边,流量为无穷大。
最大权闭合子图的权值 = 所有正权 - 最大流
个人理解:流量从源点出发,到正权代表的点,到负权代表的点,再到汇点,这个过程可以理解为选择了正权点,然后正权点的贡献被负权点抵消了。
为啥不会选择负权大于正权。因为流量都要通过正权流出,正权流出多少流量,负权就只能接受这么多流量(流量守恒),所以负权大于正权时,正负抵消,相当于不选这个正权点,也就不会选这个负权点。
因此在网络流中,最大权闭合子图=它自己正负权相减,变成了,所有正权和 -(最大权闭合子图的负权 + 会带来负贡献的正权)     

在本题中,路线(只保留正收益视为上面的正权点,树上的边视为上面的负权点,然后跑网络流就搞定了。

但是n和m都有1e4,直接建图高达1e8的边.....
可以树链剖分,然后一条路线实际上就是一个区间,再用线段树将这个区间划分成 log 个区间,将路线和这些区间连边即可。
(感觉会做CF786B,也能很轻松理解这个这题的线段树优化)

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int N = 3 + 1e4;

int n, m;

namespace Dinic {
struct Edge {
    int ver, next, flow;
} E[N * 200];
int head[N * 200], cur[N * 200], id = 1;
int maxFlow;
int d[N * 200];
int nodeId; // 用于记录当前网络流,图中有多少个点
const int s = ++nodeId; // 源
const int t = ++nodeId; // 汇

void addEdge(int u, int v, int f) {
    E[++id] = {v, head[u], f};
    head[u] = id;
    E[++id] = {u, head[v], 0};
    head[v] = id;
}
int bfs() {
    queue<int> q;
    q.push(s);
    for (int i = 1; i <= nodeId; ++i) {
        d[i] = 0;
        cur[i] = head[i];
    }
    d[s] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = cur[x]; i; i = E[i].next) {
            int y = E[i].ver;
            if (E[i].flow && !d[y]) {
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
    }
    return d[t];
}
int dfs(int x, int f) {
    if (x == t || f == 0) {
        return f;
    }
    int flow = 0;
    for (int &i = cur[x]; i && f > flow; i = E[i].next) {
        int y = E[i].ver;
        if (d[y] != d[x] + 1) {
            continue;
        }
        int t = dfs(y, min(f - flow, E[i].flow));
        flow += t;
        E[i].flow -= t;
        E[i ^ 1].flow += t;
        if (f == flow) {
            return flow;
        }
    }
    return flow;
}
int run() {
    while (bfs()) {
        maxFlow += dfs(s, 1e9);
    }
    return maxFlow;
}
};  // namespace Dinic

namespace Tree {
struct E {
    int y, id; // 边(x,y),在网络流建图中点编号为id
};
vector<E> edge[N];
int sz[N], top[N], fa[N], son[N], dfn[N], d[N], id;
int p[N]; // 边(x,y),d[x]<d[y],id存到p[y]
int w[N]; // w[i]含义,p[x]的dfs序为i,w[i]就是p[x]

struct TreeNode {
    int l, r;
    int v; // [l,r]区间代表的点在网络流建图中的点的编号
} tr[N << 2];

void addEdge(int u, int v, int id) {
    edge[u].push_back({v, id});
    edge[v].push_back({u, id});
}

void dfs1(int x, int fa) {
    d[x] = d[fa] + 1;
    sz[x] = 1;
    Tree::fa[x] = fa;
    for (auto &[y, id] : edge[x]) {
        if (y == fa) {
            continue;
        }
        p[y] = id;
        dfs1(y, x);
        sz[x] += sz[y];
        if (sz[y] > sz[son[x]]) {
            son[x] = y;
        }
    }
}

void dfs2(int x, int fa, int topf) {
    dfn[x] = ++id;
    top[x] = topf;
    w[id] = p[x];
    if (son[x]) {
        dfs2(son[x], x, topf);
    }
    for (auto &[y, id] : edge[x]) {
        if (y == fa || y == son[x]) {
            continue;
        }
        dfs2(y, x, y);
    }
}

void segmentTreeBuild(int k, int l, int r, vector<int> ve) {
    tr[k].l = l;
    tr[k].r = r;
    tr[k].v = ++Dinic::nodeId;
    ve.push_back(tr[k].v);
    if (l == r) {
        if (r != 1) { // 1号点没有存边
            for (auto x : ve) { // 将线段树区间包含r的区间,和r连边
                Dinic::addEdge(x, w[r], 1e9);
            }
        }
        return;
    }
    int mid = l + r >> 1;
    segmentTreeBuild(lson, l, mid, ve);
    segmentTreeBuild(rson, mid + 1, r, ve);
}

void update(int k, int l, int r, int t) {
    if (l <= tr[k].l && tr[k].r <= r) {
        Dinic::addEdge(t, tr[k].v, 1e9);
        return;
    }
    int mid = tr[k].l + tr[k].r >> 1;
    if (l <= mid) {
        update(lson, l, r, t);
    }
    if (r > mid) {
        update(rson, l, r, t);
    }
}

void addDinicEdge(int u, int v, int f) {
    int t = ++Dinic::nodeId;
    Dinic::addEdge(Dinic::s, t, f);
    while (top[u] != top[v]) {
        if (d[top[u]] < d[top[v]]) {
            swap(u, v);
        }
        update(1, dfn[top[u]], dfn[u], t);
        u = fa[top[u]];
    }
    if (d[u] > d[v]) {
        swap(u, v);
    }
    if (dfn[u] + 1 <= dfn[v]) {
        // u这个存在边不在范围内,不能写成update(1, dfn[u], dfn[v], t);
        update(1, dfn[u] + 1, dfn[v], t);
    }
}
}  // namespace Tree

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;

    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        Tree::addEdge(u, v, ++Dinic::nodeId);
        Dinic::addEdge(Dinic::nodeId, Dinic::t, w);
    }
    Tree::dfs1(1, 0);
    Tree::dfs2(1, 0, 1);
    Tree::segmentTreeBuild(1, 1, n, {});

    int ans = 0;

    while (m--) {
        int s, t, a, b;
        cin >> s >> t >> a >> b;
        if (a - b > 0) {
            Tree::addDinicEdge(s, t, a - b);
            ans += a - b;
        }
    }

    ans -= Dinic::run();

    cout << ans << endl;

    return 0;
}