【CF600E】Lomsat gelral——树上启发式合并

迈不过友情╰ 2021-10-29 18:54 236阅读 0赞

（题面来自luogu）

### 题意翻译 ###

一棵树有n个结点，每个结点都是一种颜色，每个颜色有一个编号，求树中每个子树的最多的颜色编号的和。

ci <= n <= 1e5

裸题。统计时先扫一遍得到出现次数最大值，然后再扫一遍看哪个颜色的出现次数与mxCnt相等。注意用一个bool数组判重，清空轻儿子贡献时要顺手把bool数组也打成false。（这是错的，请看下一份代码）

代码：

1.  \#include <iostream> 
2.  \#include <cstdio> 
3.  \#include <cctype> 
4.  \#define maxn 100010 
5.  using namespace std; 
6.  template <typename T> 
7.  void read(T &x) \{ 
8.  x = 0;
9.  char ch = getchar(); 
10. while (!isdigit(ch)) 
11. ch = getchar();
12. while (isdigit(ch)) 
13. x = x \* 10 + (ch ^ 48), ch = getchar();
14. \}
15. int n; 
16. int head\[maxn\], top; 
17. struct E \{ 
18. int to, nxt; 
19. \} edge\[maxn << 1\];
20. inline void insert(int u, int v) \{ 
21. edge\[++top\] = (E) \{v, head\[u\]\};
22. head\[u\] = top;
23. \}
24. int son\[maxn\], size\[maxn\]; 
25. long long ans\[maxn\]; 
26. void dfs1(int u, int pre) \{ 
27. size\[u\] = 1;
28. for (int i = head\[u\]; i; i = edge\[i\].nxt) \{ 
29. int v = edge\[i\].to; 
30. if (v == pre) continue; 
31. dfs1(v, u);
32. size\[u\] += size\[v\];
33. if (size\[v\] > size\[son\[u\]\]) 
34. son\[u\] = v;
35. \}
36. return; 
37. \}
38. int color\[maxn\], cnt\[maxn\], sum; 
39. int curSon, mxCnt; 
40. bool vis\[maxn\]; 
41. void calc(int u, int pre, bool op) \{ 
42. op ? (++cnt\[color\[u\]\], mxCnt = max(mxCnt, cnt\[color\[u\]\])) : (--cnt\[color\[u\]\], vis\[color\[u\]\] = false); 
43. for (int i = head\[u\]; i; i = edge\[i\].nxt) \{ 
44. int v = edge\[i\].to; 
45. if (v == pre || v == curSon) 
46. continue; 
47. calc(v, u, op);
48. \}
49. \}
50. void stats(int u, int pre) \{ 
51. if (cnt\[color\[u\]\] == mxCnt && !vis\[color\[u\]\]) 
52. sum += color\[u\], vis\[color\[u\]\] = true; 
53. for (int i = head\[u\]; i; i = edge\[i\].nxt) \{ 
54. int v = edge\[i\].to; 
55. if (v != pre) 
56. stats(v, u);
57. \}
58. return; 
59. \}
60. void dsu(int u, int pre, bool op) \{ 
61. for (int i = head\[u\]; i; i = edge\[i\].nxt) \{ 
62. int v = edge\[i\].to; 
63. if (v == pre || v == son\[u\]) 
64. continue; 
65. dsu(v, u, 0);
66. \}
67. if (son\[u\]) 
68. dsu(son\[u\], u, 1), curSon = son\[u\];
69. mxCnt = 0;
70. calc(u, pre, 1);
71. stats(u, pre);
72. ans\[u\] = sum;
73. curSon = 0;
74. if (!op) \{ 
75. sum = 0;
76. calc(u, pre, 0);
77. \}
78. \}
79. int main() \{ 
80. read(n);
81. for (int i = 1; i <= n; ++i) 
82. read(color\[i\]);
83. int u, v; 
84. for (int i = 1; i < n; ++i) \{ 
85. read(u), read(v);
86. insert(v, u), insert(u, v);
87. \}
88. dfs1(1, 0);
89. dsu(1, 0, 1);
90. for (int i = 1; i <= n; ++i) 
91. printf("%I64d ", ans\[i\]); 
92. return 0; 
93. \}

（交这个题的时候cf炸了……才不是因为我TLE呢

\--------------------------

然而果然出了锅，昨天CF评测机大概是被这个弱智错误笑死的……

重测了下，上面那份代码是错的，原因是没有考虑重儿子内的最大出现次数。然而原思路越改越复杂，后来想了想，每遍历到重复的颜色其出现次数都会+1，因此不用判重，从每个点统计时扫一遍就好了。

代码：

1.  \#include <iostream> 
2.  \#include <cstdio> 
3.  \#include <cctype> 
4.  \#define maxn 100010 
5.  using namespace std; 
6.  template <typename T> 
7.  void read(T &x) \{ 
8.  x = 0;
9.  char ch = getchar(); 
10. while (!isdigit(ch)) 
11. ch = getchar();
12. while (isdigit(ch)) 
13. x = x \* 10 + (ch ^ 48), ch = getchar();
14. \}
15. int n; 
16. int head\[maxn\], top; 
17. struct E \{ 
18. int to, nxt; 
19. \} edge\[maxn << 1\];
20. inline void insert(int u, int v) \{ 
21. edge\[++top\] = (E) \{v, head\[u\]\};
22. head\[u\] = top;
23. \}
24. int son\[maxn\], size\[maxn\]; 
25. long long ans\[maxn\]; 
26. void dfs1(int u, int pre) \{ 
27. size\[u\] = 1;
28. for (int i = head\[u\]; i; i = edge\[i\].nxt) \{ 
29. int v = edge\[i\].to; 
30. if (v == pre) continue; 
31. dfs1(v, u);
32. size\[u\] += size\[v\];
33. if (size\[v\] > size\[son\[u\]\]) 
34. son\[u\] = v;
35. \}
36. return; 
37. \}
38. int color\[maxn\], cnt\[maxn\]; 
39. long long sum; 
40. int curSon, mxCnt; 
41. void calc(int u, int pre, int val) \{ 
42. cnt\[color\[u\]\] += val;
43. if (val == 1) \{ 
44. if (cnt\[color\[u\]\] > mxCnt) 
45. mxCnt = cnt\[color\[u\]\], sum = color\[u\];
46. else if (cnt\[color\[u\]\] == mxCnt) 
47. sum += color\[u\];
48. \}
49. for (int i = head\[u\]; i; i = edge\[i\].nxt) \{ 
50. int v = edge\[i\].to; 
51. if (v == pre || v == curSon) 
52. continue; 
53. calc(v, u, val);
54. \}
55. \}
56. void dsu(int u, int pre, bool op) \{ 
57. for (int i = head\[u\]; i; i = edge\[i\].nxt) \{ 
58. int v = edge\[i\].to; 
59. if (v == pre || v == son\[u\]) 
60. continue; 
61. dsu(v, u, 0);
62. \}
63. if (son\[u\]) 
64. dsu(son\[u\], u, 1), curSon = son\[u\];
65. calc(u, pre, 1);
66. ans\[u\] = sum;
67. curSon = 0;
68. if (!op) \{ 
69. mxCnt = sum = 0;
70. calc(u, pre, -1);
71. \}
72. \}
73. int main() \{ 
74. read(n);
75. for (int i = 1; i <= n; ++i) 
76. read(color\[i\]);
77. int u, v; 
78. for (int i = 1; i < n; ++i) \{ 
79. read(u), read(v);
80. insert(v, u), insert(u, v);
81. \}
82. dfs1(1, 0);
83. dsu(1, 0, 1);
84. for (int i = 1; i <= n; ++i) 
85. printf("%I64d ", ans\[i\]); 
86. return 0; 
87. \}

转载于:https://www.cnblogs.com/TY02/p/11323015.html