Problem
题意:
给你一个以 \(1\) 为根节点的有根树,每个节点有一个权值。求以每一个节点为根的子树的权值众数的和。
Solution
\(\operatorname{Algorithm 1}\) : dfs序 + 莫队
我们可以将问题转化一下,求出每个节点的 \(\operatorname{dfs}\) 序,将每个子树转化成序列上得一段区间。
所以询问每个点的子树,就变成了询问 \(\operatorname{dfn}\) 序列的某个区间。
对于这种区间维护众数,并且没有在线离线要求得题目,很容易想到用莫队去处理。
为了使莫队更高效,到达 \(\operatorname{O(n\sqrt{n})}\) 的复杂度,我们需要将每次增加或删去一个点的过程用 \(\operatorname{O(1)}\) 来维护。
可以设 \(ct_i\) 表示权值 \(i\) 出现的次数,\(ret_i\) 表示出现 \(i\) 的权值的和。
- 对于增加一个点,就相当于使 \(ct_i+1\),先减去原来的贡献,再看 \(ct_i\) 能否对众数做出贡献,或者更新众数。
- 对于减去一个点,就是使得 \(ct_i-1\),先减去原来的贡献,再看众数是否会变。
其他的就是莫队的板子了。。。
code of Algorithm 1
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#define int long long //无伤大雅
using namespace std;
const int Maxn = 1e5;
int n, cnt, maxn;
int ret[Maxn + 5], mp[Maxn + 5];
int c[Maxn + 5], in[Maxn + 5], out[Maxn + 5], ans[Maxn + 5], pos[Maxn + 5], ct[Maxn + 5];
vector < int > edge[Maxn + 5];
struct Node {
int id, l, r;
friend bool operator < (Node x, Node y) {
return pos[x.l] == pos[y.l] ? x.r < y.r : x.l < y.l;
}
} q[Maxn + 5];
void DFS (int u) {
in[u] = ++ cnt;
mp[cnt] = u;
for (int i = 0; i < (int) edge[u].size (); i ++) {
if (in[edge[u][i]]) continue;
DFS (edge[u][i]);
}
out[u] = cnt;
}
void Add (int x) {
x = mp[x];
if (ct[c[x]]) ret[ct[c[x]]] -= c[x];
ct[c[x]] ++;
ret[ct[c[x]]] += c[x];
if (ct[c[x]] > maxn) {
maxn = ct[c[x]];
}
}
void Del (int x) {
x = mp[x];
ret[ct[c[x]]] -= c[x];
if (ct[c[x]] == maxn && ret[maxn] == 0) {
maxn = ct[c[x]] - 1;
}
ct[c[x]] --;
if (ct[c[x]]) ret[ct[c[x]]] += c[x];
}
signed main () {
scanf ("%lld", &n);
for (int i = 1; i <= n; i ++) {
scanf ("%lld", &c[i]);
}
for (int i = 1, u, v; i < n; i ++) {
scanf ("%lld %lld", &u, &v);
edge[u].push_back (v);
edge[v].push_back (u);
}
DFS (1);
for (int i = 1; i <= n; i ++) {
q[i].id = i;
q[i].l = in[i], q[i].r = out[i];
}
int t = sqrt (n);
for (int i = 1; i <= n; i ++) {
pos[in[i]] = in[i] / t;
}
sort (q + 1, q + 1 + n);
int l = 1, r = 0;
for (int i = 1; i <= n; i ++) {
while (l > q[i].l) Add (-- l);
while (r < q[i].r) Add (++ r);
while (l < q[i].l) Del (l ++);
while (r > q[i].r) Del (r --);
ans[q[i].id] = ret[maxn];
}
for (int i = 1; i <= n; i ++) {
printf ("%lld ", ans[i]);
}
return 0;
}
\(\operatorname{Algorithm 2}\) : dfs序 + 分块
这种做法是可以在线的,dfn 之后的做法与 “数列分块9” 的做法差不多,我没有写,也不想写。
\(\operatorname{Algorithm 3}\) : 线段树合并
这种做法就比较直接。对于一个节点,它的每一个子节点的子树所存的信息是独立的,为了求得还节点的答案,是需要将它的每一个子节点的子树的信息综合起来的。而对于这种众数的信息,我们可以用权值线段树进行存储。对于每个节点,再将它的子树合并起来,就能求得答案。
code of Algorithm 3
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Maxn = 1e5;
int n, tot, node;
LL ret[Maxn + 5];
int head[Maxn + 5], a[Maxn + 5], vis[Maxn + 5], rt[Maxn + 5];
struct Edge {
int ver, nxt;
Edge () {}
Edge (int u, int v) { ver = u, nxt = v; }
} edge[(Maxn << 1) + 5];
struct Segment_Tree {
int lc, rc, sum;
LL ans;
#define lc(x) t[x].lc
#define rc(x) t[x].rc
#define sum(x) t[x].sum
#define ans(x) t[x].ans
} t[Maxn * 50 + 5];
int read () {
int x = 0, f = 1; char c = getchar ();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar (); }
while ('0' <= c && c <= '9') { x = (x << 1) + (x << 3) + c - '0'; c = getchar (); }
return x * f;
}
void add (int u, int v) {
edge[++ tot] = Edge (v, head[u]); head[u] = tot;
}
void Pushup (int u) {
if (sum (lc (u)) > sum (rc (u))) {
sum (u) = sum (lc (u));
ans (u) = ans (lc (u));
}
else if (sum (lc (u)) < sum (rc (u))) {
sum (u) = sum (rc (u));
ans (u) = ans (rc (u));
}
else {
sum (u) = sum (lc (u));
ans (u) = ans (lc (u)) + ans (rc (u));
}
}
void Insert (int &pos, int l, int r, int x) {
if (!pos) pos = ++ node;
if (l == r) { sum (pos) ++, ans (pos) = l; return ; }
int mid = l + r >> 1;
if (x <= mid) Insert (lc (pos), l, mid, x);
else Insert (rc (pos), mid + 1, r, x);
Pushup(pos);
}
int Merge (int x, int y, int l, int r) {
if (!x || !y) return x + y;
if (l == r) { sum (x) += sum (y); ans (x) = l; return x; }
int mid = l + r >> 1;
lc (x) = Merge (lc (x), lc (y), l, mid);
rc (x) = Merge (rc (x), rc (y), mid + 1, r);
Pushup (x);
return x;
}
void dfs (int u) {
vis[u] = 1;
Insert (rt[u], 1, n, a[u]);
for (int i = head[u], v; i; i = edge[i].nxt) {
v = edge[i].ver;
if (vis[v]) continue;
dfs (v);
Merge (rt[u], rt[v], 1, n);
}
ret[u] = ans (rt[u]);
}
int main () {
n = read ();
for (int i = 1; i <= n; i ++) scanf ("%d", &a[i]);
for (int i = 1, u, v; i < n; i ++) {
u = read (), v = read ();
add (u, v), add (v, u);
}
dfs (1);
for (int i = 1; i <= n; i ++) printf ("%lld ", ret[i]);
return 0;
}