@CQUPTacm
2018-11-13T00:12:07.000000Z
字数 2163
阅读 1410
里题解
这是一棵无根树,我们可以定义任意一个点为根(),根据这棵树我们定义一些变量:
我们可以得到结论:
考虑树dp,用一个集合 来表示 中所有能到达深度 的点的边集,按照边权排序。
因为我们在算答案时,只有 对答案有贡献,所以在合并 与 时,我们可以将边 (v, f, cost) 转换成边 (u, f, cost - ex_cost[v] + ex_cost[u]), 并将 f==u 的点从集合中删除。
但是考虑树是一整条链的情况,每次合并集合的大小分别为 每次合并集合的复杂度为 ,那么总复杂度就达到了 ,所以是会超时的。
我们在合并的时候考虑遍历 小的集合,把它的元素插到大集合上,那么在每个点都有 个子节点时达到最坏复杂度,复杂度为 , 为树的高度,显然 。
我们令 为 中合并后的根,那么对于边 (r[v], f, cost) 它实际上是被转换为了 (r[u], f, cost - ex_cost[r[v]] + 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;
}