Codeforces 348E 树的中心点的性质 / 树形DP / 点分治

港控/mmm° 2021-12-12 02:04 340阅读 0赞

题意及思路:http://ydc.blog.uoj.ac/blog/12

在求出树的直径的中心后,以它为根,对于除根以外的所有子树,求出子树中的最大深度,以及多个点的最大深度的lca,因为每个点的最长路径一定经过根,所以找到最大深度的子树,然后在这个点和最大深度的lca上树上差分一下就好了。注意,此处的中心是sum / 2处的那个点(sum是直径的长度)

代码:

  1. #include <bits/stdc++.h>
  2. #define pii pair<int, int>
  3. using namespace std;
  4. const int maxn = 100010;
  5. int f[maxn];
  6. int d[maxn];
  7. vector<pii> G[maxn];
  8. int mx[maxn], mx_pos[maxn], dye[maxn], sum[maxn];
  9. int v[maxn];
  10. int ans, ans_cnt, root, pos, n, m;
  11. void add(int x, int y, int z) {
  12. G[x].push_back(make_pair(y, z));
  13. G[y].push_back(make_pair(x, z));
  14. }
  15. bool dfs(int x, int fa, int now) {
  16. int flag = (v[x] == 1);
  17. d[x] = now;
  18. for (auto y : G[x]) {
  19. if(y.first == fa) continue;
  20. int tmp = dfs(y.first, x, now + y.second);
  21. flag |= tmp;
  22. f[y.first] = x;
  23. }
  24. if(flag && d[x] > ans) {
  25. ans = d[x];
  26. pos = x;
  27. }
  28. return flag;
  29. }
  30. void get_root() {
  31. dfs(1, -1, 0);
  32. memset(d, 0, sizeof(d));
  33. ans = 0;
  34. root = pos;
  35. dfs(root, -1, 0);
  36. int Sum = d[pos], tmp = pos;
  37. while(d[tmp] > d[pos] / 2) {
  38. tmp = f[tmp];
  39. }
  40. root = tmp;
  41. }
  42. void update(int pos, int ch, int val) {
  43. if(mx[pos] < mx[ch] + val) {
  44. mx[pos] = mx[ch] + val;
  45. mx_pos[pos] = mx_pos[ch];
  46. } else if(mx[pos] == mx[ch] + val) {
  47. mx_pos[pos] = pos;
  48. }
  49. }
  50. bool dfs1(int x, int fa, int color) {
  51. dye[x] = color;
  52. int flag = (v[x] == 1);
  53. if(flag == 1) mx_pos[x] = x;
  54. for (auto y : G[x]) {
  55. if(y.first == fa) continue;
  56. int tmp;
  57. tmp = dfs1(y.first, x, color);
  58. f[y.first] = x;
  59. if(tmp) {
  60. update(x, y.first, y.second);
  61. }
  62. flag |= tmp;
  63. }
  64. return flag;
  65. }
  66. void dfs2(int x, int fa) {
  67. for (auto y : G[x]) {
  68. if(y.first == fa) continue;
  69. dfs2(y.first, x);
  70. sum[x] += sum[y.first];
  71. }
  72. if(sum[x] > ans && v[x] == 0) {
  73. ans = sum[x];
  74. ans_cnt = 1;
  75. } else if(sum[x] == ans && v[x] == 0) {
  76. ans_cnt++;
  77. }
  78. }
  79. vector<pii> res;
  80. map<int, int> mp;
  81. set<int> s;
  82. int tot;
  83. void solve() {
  84. for (auto y : G[root]) {
  85. int tmp = dfs1(y.first, root, ++tot);
  86. if(tmp) {
  87. res.push_back(make_pair(mx[y.first] + y.second, mx_pos[y.first]));
  88. }
  89. }
  90. if(v[root] == 1) {
  91. res.push_back(make_pair(0, root));
  92. }
  93. sort(res.begin(), res.end());
  94. s.insert(dye[res[res.size() - 1].second]);
  95. for (int i = res.size() - 1; i >= 1; i--) {
  96. if(res[i].first == res[i - 1].first) {
  97. s.insert(dye[res[i].second]);
  98. s.insert(dye[res[i - 1].second]);
  99. } else {
  100. break;
  101. }
  102. }
  103. for (int i = 0; i < res.size(); i++) {
  104. mp[res[i].first]++;
  105. }
  106. for (int i = 1; i <= n; i++) {
  107. if(v[i] == 1) {
  108. if(s.count(dye[i]) && s.size() > 1) {
  109. if(s.size() > 2) {
  110. sum[i]++;
  111. } else {
  112. for (int j = res.size() - 1; j >= 0; j--) {
  113. if(dye[i] != dye[res[j].second]) {
  114. sum[i]++;
  115. sum[res[j].second]++;
  116. sum[root]--;
  117. break;
  118. }
  119. }
  120. }
  121. } else {
  122. if(s.size() > 1) {
  123. sum[i]++;
  124. continue;
  125. }
  126. if(dye[i] != dye[res[res.size() - 1].second]) {
  127. sum[i]++;
  128. sum[res[res.size() - 1].second]++;
  129. sum[root]--;
  130. }
  131. else {
  132. sum[i]++;
  133. if(mp[res[res.size() - 2].first] == 1) {
  134. sum[res[res.size() - 2].second]++;
  135. sum[root]--;
  136. }
  137. }
  138. }
  139. }
  140. }
  141. ans = ans_cnt = 0;
  142. dfs2(root, -1);
  143. }
  144. int main() {
  145. int x, y, z;
  146. scanf("%d%d", &n, &m);
  147. for (int i = 1; i <= m ;i++) {
  148. scanf("%d", &x);
  149. v[x] = 1;
  150. }
  151. for (int i = 1; i < n; i++) {
  152. scanf("%d%d%d", &x, &y, &z);
  153. add(x, y, z);
  154. }
  155. get_root();
  156. solve();
  157. printf("%d %d\n", ans, ans_cnt);
  158. }

 树形DP做法:我们不用树的直径中心的性质,可以通过树形DP求出最长链。怎么DP呢?首先对于每个点,我们维护在这颗子树中的所有点中,到这个点的最远的和次远的距离,以及这些点的LCA, 个数这些信息。之后,我们再DP一遍。到一个点的最路径,只有两种情况,一种是在子树内,一种是在子树外。对于在子树外的情况,我们可以通过到这个点的父亲节点的最长路径和自己的最长路径/次长路径,来确定到这个点的最长路径,然后去更新子树。剩下的操作和直径中心的操作一样了。

马上期末考试了,太忙了,代码先咕了,有时间再补QAQ

点分治做法继续留坑QAQ

转载于:https://www.cnblogs.com/pkgunboat/p/11000188.html

发表评论

表情:
评论列表 (有 0 条评论,340人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Codeforces 750E 线段DP

    题意:给你一个字符串,有两种操作:1:把某个位置的字符改变。2:询问l到r的子串最少需要删除多少个字符,使得这个子串含有2017子序列,并且没有2016子序列? 思路:线段树

    相关 Codeforces 735E 树形DP

    题意:给你一棵树,你需要在这棵树上选择一些点染成黑色,要求染色之后树中任意节点到离它最近的黑色节点的距离不超过m,问满足这种条件的染色方案有多少种? 思路:设dp\[x\]\

    相关 Codeforces 633F 直径/树形DP

    题意:有两个小孩玩游戏,每个小孩可以选择一个起始点,并且下一个选择的点必须和自己选择的上一个点相邻,问两个选的点权和的最大值是多少? 思路:首先这个问题可以转化为求树上两不相

    相关 Codeforces 1101D 分治

    题意:有一颗树,每个点有一个点权,边权都是1,问路径上的所有点的gcd不是1的最长路径是多少? 思路:之前补这道题的时候,用分解质因数 + 树形DP做的,其实用点分治可以更暴