Codeforces 600E
题意：一棵树$n$个节点，已知点权$ci \leq n$，根为1 对于每个节点，求出对应子树中，出现次数最多（或之一）的点权的和
这题询问子树可以用 DFS 序，然后在 DFS 序上维护出现次数最多（或之一）的点权的和即可。
可以使用莫队对每个子树进行维护。
开数组col1 每种颜色出现的次数col2 每种次数的答案
然后更新即可，具体看代码的adjustAdd扩充当前区间，和adjustSub缩小当前区间
知识点：
莫队的扩充区间放在缩小区间前可以避免出现某些问题
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const LL MAXN = 100000 + 5;
LL bl[MAXN], blolen;
struct query {
LL l, r, id;
bool operator < (const query &b) const {
if (bl[l] == bl[b.l]) return r < b.r;
return bl[l] < bl[b.l];
}
}q[MAXN];
LL n, c[MAXN], sz, dfn[MAXN], col1[MAXN], col2[MAXN], nl, nr, mks, ans[MAXN];
vector<LL> G[MAXN];
void ins(LL x, LL y) {G[x].push_back(y), G[y].push_back(x);}
void dfs(LL u, LL pa) {
q[u].l = ++sz, dfn[sz] = u, q[u].id = u;
for (LL i = 0; i < (LL)G[u].size(); i++) {
LL v = G[u][i];
if (v != pa) dfs(v, u);
}
q[u].r = sz;
}
//col1: 每种颜色出现的次数; col2: 每种次数的答案
void adjustAdd(LL x) {
x = dfn[x];
col1[c[x]]++;
col2[col1[c[x]] - 1] -= c[x];
col2[col1[c[x]]] += c[x];
if (col1[c[x]] > mks) mks = col1[c[x]];
}
void adjustSub(LL x) {
x = dfn[x];
col1[c[x]]--;
col2[col1[c[x]] + 1] -= c[x];
col2[col1[c[x]]] += c[x];
if (col2[col1[c[x]] + 1] == 0 && mks == col1[c[x]] + 1) mks--;
}
void clean() {
ms(col1, 0), ms(col2, 0), sz = 0;
}
int solve() {
clean();
blolen = sqrt(n);
for (LL i = 1; i <= n; i++) scanf("%I64d", &c[i]), bl[i] = (i - 1) / blolen + 1;
for (LL x, y, i = 1; i < n; i++) scanf("%I64d%I64d", &x, &y), ins(x, y);
dfs(1, 0);
sort(q + 1, q + 1 + n);
nl = 1, nr = 0, mks = 1;
for (LL i = 1; i <= n; i++) {
while (nr < q[i].r) adjustAdd(nr + 1), nr++;
while (nl > q[i].l) adjustAdd(nl - 1), nl--;
while (nl < q[i].l) adjustSub(nl), nl++;
while (nr > q[i].r) adjustSub(nr), nr--;
ans[q[i].id] = col2[mks];
}
for (LL i = 1; i <= n; i++) printf("%I64d ", ans[i]);
return 0;
}
int main() {
scanf("%I64d", &n), solve();
return 0;
}
dsu on tree
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
int n, c[MAXN], idx, dfn[MAXN], siz[MAXN], son[MAXN], ll[MAXN], rr[MAXN], tax[MAXN], maxd;
LL cnt, ans[MAXN];
vector<int > G[MAXN];
void ins(int x, int y) {G[x].push_back(y);}
void add(int x) {if (++tax[x] > maxd) maxd = tax[x], cnt = x; else if (tax[x] == maxd) cnt += x;}
void del(int x) {--tax[x];}
void dfs_pre(int u, int fa) {
ll[u] = ++idx, siz[u] = 1, dfn[idx] = u, son[u] = -1;
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa) {
dfs_pre(v, u);
if (son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
siz[u] += siz[v];
}
}
rr[u] = idx;
}
void dfs_dsu(int u, int fa, int kp) {
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa && v != son[u]) dfs_dsu(v, u, 0);
} // 轻儿子先处理，不保留
if (son[u] != -1) dfs_dsu(son[u], u, 1); // 处理重儿子，保留
for (int o = 0; o < (int)G[u].size(); ++o) {
int v = G[u][o];
if (v != fa && v != son[u])
for (int i = ll[v]; i <= rr[v]; ++i) add(c[dfn[i]]); // 暴力轻儿子
}
add(c[u]);
ans[u] = cnt; // 统计答案
if (!kp) {for (int i = ll[u]; i <= rr[u]; ++i) del(c[dfn[i]]); cnt = maxd = 0;} // 删除
}
void clean() {}
int solve() {
clean();
cin >> n;
for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
for (int x, y, i = 1; i < n; ++i) {
scanf("%d%d", &x, &y);
ins(x, y), ins(y, x);
}
dfs_pre(1, 0);
dfs_dsu(1, 0, 0);
for (int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
*/
