CF600E Lomsat gelral 题解

欢迎访问我的博客：blog.chungzh.cn

线段树合并模板题。

做的时候脑残，在动态开点新的一个线段树时忘记写 pushup 了，出了一些奇怪的错误。

对于每一个点都维护一棵权值线段树，记录最大出现次数和满足次数最大的的编号和，然后按照 DFS 序依次线段树合并，就可以求出当前子树的答案。

关键在于 pushup 的写法，当两边最大出现次数相等时，颜色编号相加。否则，取次数较大的一边做答案。

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100005;
int n;
long long ans[MAXN], sum[MAXN << 5];
int c[MAXN], root[MAXN], times[MAXN << 5], lc[MAXN << 5], rc[MAXN << 5],
    tot;
vector<int> g[MAXN];
void pushup(int u) {
  times[u] = max(times[lc[u]], times[rc[u]]);
  if (times[lc[u]] > times[rc[u]]) {
    sum[u] = sum[lc[u]];
  } else if (times[lc[u]] < times[rc[u]]) {
    sum[u] = sum[rc[u]];
  } else {
    sum[u] = sum[lc[u]] + sum[rc[u]];
  }
}
void update(int& u, int c, int l = 1, int r = n) {
  if (!u) u = ++tot;
  if (l == r) {
    sum[u] = c;
    times[u] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (c <= mid)
    update(lc[u], c, l, mid);
  else
    update(rc[u], c, mid + 1, r);
  pushup(u);
}
int merge(int u, int v, int l = 1, int r = n) {
  if (!u || !v) return u ^ v;
  if (l == r) {
    times[u] += times[v];
    return u;
  }
  int mid = (l + r) >> 1;
  lc[u] = merge(lc[u], lc[v], l, mid);
  rc[u] = merge(rc[u], rc[v], mid + 1, r);
  pushup(u);
  return u;
}
void dfs(int u, int fa = -1) {
  update(root[u], c[u]);
  if (g[u][0] == fa && g[u].size() == 1) {  // 叶子
    ans[u] = c[u];
    return;
  }
  for (auto i : g[u]) {
    if (i == fa) continue;
    dfs(i, u);
    root[u] = merge(root[u], root[i]);
  }
  ans[u] = sum[root[u]];
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> c[i];
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1);
  for (int i = 1; i <= n; i++) { cout << ans[i] << ' '; }
  return 0;
}

CF600E 题解

给定一棵 $n$ 个节点，$1$ 号节点为根节点的树，每个节点有权值 $c_i$。求出以所有节点为根的子树内出现次数最多的权值的和（因为可能有多个最大权值）。

$1 \le n \le 10^5$，$1 \le c_i \le n$。

线段树合并裸题。 对于每个节点开一棵权值线段树，维护区间最大最大值和所有最大值的和， $\tt{dfs}$ 合并线段树即可。

注意答案可以达到 $10 ^ 5 \times 10 ^ 5 = 10 ^ {10}$，别忘了 longlong。

#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}

#define N 100010
#define pb push_back

int n, a[N], rt[N];
long long res[N];
vector<int> e[N];

struct Segment_tree {
	int l, r, ls, rs;
	long long Mx, sum;
	#define lid tr[id].ls
	#define rid tr[id].rs
}tr[N * 20]; int cnt = 0;
int New() {return ++ cnt;}
void pushup(int id) {
	tr[id].Mx = max(tr[lid].Mx, tr[rid].Mx);
	if (tr[lid].Mx > tr[rid].Mx) tr[id].sum = tr[lid].sum;
	if (tr[lid].Mx < tr[rid].Mx) tr[id].sum = tr[rid].sum;
	if (tr[lid].Mx == tr[rid].Mx) tr[id].sum = tr[lid].sum + tr[rid].sum;
}
void Add(int &id, int l, int r, int x) {
	if (!id) id = New();
	tr[id].l = l, tr[id].r = r;
	if (l == r) {
		tr[id].Mx = 1, tr[id].sum = x;
		return;
	}
	int mid = tr[id].l + tr[id].r >> 1;
	if (x <= mid) Add(lid, l, mid, x);
	if (x > mid) Add(rid, mid + 1, r, x);
	pushup(id);
}
void Merge(int &x, int y, int l, int r) {
	if (!y) return;
	if (!x) return x = y, void();
	if (l == r) {
		tr[x].Mx += tr[y].Mx;
		return;
	}
	int mid = l + r >> 1;
	Merge(tr[x].ls, tr[y].ls, l, mid);
	Merge(tr[x].rs, tr[y].rs, mid + 1, r);
	pushup(x);
}

void dfs(int x, int fa) {
	Add(rt[x] = New(), 1, n, a[x]);
	for (auto y : e[x]) if (y != fa) {
		dfs(y, x), Merge(rt[x], rt[y], 1, n);
	}
	res[x] = tr[rt[x]].sum;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i ++) {
		a[i] = read();
	}
	for (int i = 1; i < n; i ++) {
		int x = read(), y = read();
		e[x].pb(y), e[y].pb(x);
	}

	dfs(1, 0);

	for (int i = 1; i <= n; i ++) {
		printf("%lld ", res[i]);
	} puts("");
	return 0;
}