搜集宝石

里题解

这是一棵无根树，我们可以定义任意一个点为根（$root$），根据这棵树我们定义一些变量：

• $fa[u]$ 表示节点 $u$ 的父亲, $pre[u]$ 表示 $u$ 与 $fa[u]$ 之间的边
• $deep[u]$ 表示节点 $u$ 的深度，$deep[u] = deep[fa[u]] + 1$
• $son[u]$ 表示 $u$ 的儿子集合
• $subtree[u]$ 表示以 $u$ 为根的子树
• $cost[u]$ 表示以 $u$ 为 $subtree[u]$ 中所有边的宝石被取完时的最小花费
• $pre\_cost[u]$ 表示 $subtree[u]$ 中所有边以及 $pre[u]$ 的宝石被取完时的最小花费
• $ex\_cost[u] = pre\_cost[u] - cost[u]$
• $w[u][d]$ 表示从 $u$ 出发能够到达一个深度 $\leq d$ 的点的边集中的最小花费

我们可以得到结论：

1. $cost[u]=\sum pre\_cost[v], v \in son[u]$
2. $pre\_cost[u] = cost[u] + min(w[u][deep[fa[u]]], w[v][deep[fa[u]]] - ex\_cost[v]) \\ \to ex\_cost[u] = min(w[u][deep[fa[u]]], w[v][deep[fa[u]]] - ex\_cost[v])$
3. $answer = cost[root] = \sum ex\_cost[u]$

考虑树dp，用一个集合 $s_u$ 来表示 $subtree[u]$ 中所有能到达深度 $\leq deep[fa[u]]$ 的点的边集，按照边权排序。

因为我们在算答案时，只有 $ex\_cost[u]$ 对答案有贡献，所以在合并 $s_u$ 与 $s_v$ 时，我们可以将边 (v, f, cost) 转换成边 (u, f, cost - ex_cost[v] + ex_cost[u])， 并将 f==u 的点从集合中删除。

但是考虑树是一整条链的情况，每次合并集合的大小分别为 $1,2,\cdots,n$ 每次合并集合的复杂度为 $O(size)$，那么总复杂度就达到了 $O(n^2)$，所以是会超时的。

我们在合并的时候考虑遍历 $size$ 小的集合，把它的元素插到大集合上，那么在每个点都有 $2$ 个子节点时达到最坏复杂度，复杂度为 $O(hn)$，$h$ 为树的高度，显然 $h=log_2(n)$。

我们令 $r[u]$ 为 $subtree[u]$ 中合并后的根，那么对于边 (r[v], f, cost) 它实际上是被转换为了 (r[u], f, cost - ex_cost[r[v]] + ex_cost[r[u]])

这时候 $cost[root] = \sum ex\_cost[r[u]]$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005;
int root[N], d[N];
struct node {
    ll w;
    int v;
    node(ll _w=0, int _v=0):w(_w), v(_v) {}
    bool operator < (const node &rhs) const {
        return w==rhs.w?d[v]<d[rhs.v]:w<rhs.w;
    }
};
vector<int> g[N];
vector<node> g1[N];
ll ex_cost[N], res;
set <node> s[N];
void dfs(int u, int fa) {
    for (int i=0;i<g1[u].size();++i)
        s[u].insert(g1[u][i]);
    root[u] = u; 
    for (int i=0;i<g[u].size(); ++i) {
        int v=g[u][i];
        if (v == fa) continue;
        d[v] = d[u] + 1;
        dfs(v, u);
        if (s[v].empty()) {
            swap(s[u], s[v]);
            return;
        }
        ll dis = ex_cost[root[u]] - ex_cost[root[v]];
        if (s[v].size() > s[u].size()) {
            dis = -dis;
            swap(s[u], s[v]);
            root[u] = root[v];
        }
        for (set<node>::iterator it = s[v].begin(); it != s[v].end(); ++it) {
            if (it->v == u) continue; 
            s[u].insert(node(it->w+dis,it->v));
        }
    }
    while (s[u].size() && d[s[u].begin()->v] >= d[u]) s[u].erase(s[u].begin());
    if (s[u].size()) {
        ex_cost[u] = s[u].begin()->w - ex_cost[root[u]]; 
        res += ex_cost[u];
        if (root[u] != u) ex_cost[root[u]] += ex_cost[u];
    } else if (u != 1)
        res = -1; 
    return;
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 0, u, v; i < m; ++i) {
        ll w;
        scanf("%d %d %lld", &u, &v, &w);
        g1[u].push_back(node(w, v));
    }
    dfs(1, 1);
    cout << res << endl;
    return 0;
}