（题面来自luogu）

题意翻译

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

ci <= n <= 1e5

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

代码：

1. #include 

2. #include 

3. #include 

4. #define maxn 100010

5. using namespace std;

6. template 

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，因此不用判重，从每个点统计时扫一遍就好了。

代码：