[关闭]
@CQUPTacm 2018-11-12T16:12:07.000000Z 字数 2163 阅读 461

搜集宝石

里题解


这是一棵无根树,我们可以定义任意一个点为根(),根据这棵树我们定义一些变量:

我们可以得到结论:

考虑树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]])

这时候

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 300005;
  5. int root[N], d[N];
  6. struct node {
  7. ll w;
  8. int v;
  9. node(ll _w=0, int _v=0):w(_w), v(_v) {}
  10. bool operator < (const node &rhs) const {
  11. return w==rhs.w?d[v]<d[rhs.v]:w<rhs.w;
  12. }
  13. };
  14. vector<int> g[N];
  15. vector<node> g1[N];
  16. ll ex_cost[N], res;
  17. set <node> s[N];
  18. void dfs(int u, int fa) {
  19. for (int i=0;i<g1[u].size();++i)
  20. s[u].insert(g1[u][i]);
  21. root[u] = u;
  22. for (int i=0;i<g[u].size(); ++i) {
  23. int v=g[u][i];
  24. if (v == fa) continue;
  25. d[v] = d[u] + 1;
  26. dfs(v, u);
  27. if (s[v].empty()) {
  28. swap(s[u], s[v]);
  29. return;
  30. }
  31. ll dis = ex_cost[root[u]] - ex_cost[root[v]];
  32. if (s[v].size() > s[u].size()) {
  33. dis = -dis;
  34. swap(s[u], s[v]);
  35. root[u] = root[v];
  36. }
  37. for (set<node>::iterator it = s[v].begin(); it != s[v].end(); ++it) {
  38. if (it->v == u) continue;
  39. s[u].insert(node(it->w+dis,it->v));
  40. }
  41. }
  42. while (s[u].size() && d[s[u].begin()->v] >= d[u]) s[u].erase(s[u].begin());
  43. if (s[u].size()) {
  44. ex_cost[u] = s[u].begin()->w - ex_cost[root[u]];
  45. res += ex_cost[u];
  46. if (root[u] != u) ex_cost[root[u]] += ex_cost[u];
  47. } else if (u != 1)
  48. res = -1;
  49. return;
  50. }
  51. int main() {
  52. int n, m;
  53. scanf("%d %d", &n, &m);
  54. for (int i = 1, u, v; i < n; ++i) {
  55. scanf("%d %d", &u, &v);
  56. g[u].push_back(v);
  57. g[v].push_back(u);
  58. }
  59. for (int i = 0, u, v; i < m; ++i) {
  60. ll w;
  61. scanf("%d %d %lld", &u, &v, &w);
  62. g1[u].push_back(node(w, v));
  63. }
  64. dfs(1, 1);
  65. cout << res << endl;
  66. return 0;
  67. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注