「CF600E」Lomsat gelral

传送门

Luogu

解题思路

线段树合并板子题（也可以 dsu on the tree）

好像没什么好讲的，就是要注意开 long long 。

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

 	s = 0; int f = 0; char c = getchar();

 	while (!isdigit(c)) f |= (c == '-'), c = getchar();

 	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

 	s = f ? -s : s;

}

typedef long long LL;

const int _ = 100010;

int tot, head[_], nxt[_ << 1], ver[_ << 1];

inline void Add_edge(int u, int v)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }

int n, c[_];

int cnt, rt[_], lc[_ << 5], rc[_ << 5];

LL mx[_ << 5], col[_ << 5], ans[_];

inline void pushup(int p) {

	if (mx[lc[p]] > mx[rc[p]]) mx[p] = mx[lc[p]], col[p] = col[lc[p]];

	if (mx[lc[p]] < mx[rc[p]]) mx[p] = mx[rc[p]], col[p] = col[rc[p]];

	if (mx[lc[p]] == mx[rc[p]]) mx[p] = mx[lc[p]], col[p] = col[lc[p]] + col[rc[p]];

}

inline void update(int& p, int x, int l = 1, int r = n) {

	if (!p) p = ++cnt;

	if (l == r) { ++mx[p], col[p] = l; return; }

	int mid = (l + r) >> 1;

	if (x <= mid) update(lc[p], x, l, mid);

	else update(rc[p], x, mid + 1, r);

	pushup(p);

}

inline int merge(int x, int y, int l = 1, int r = n) {

	if (!x || !y) return x + y;

	if (l == r)

		return mx[x] += mx[y], col[x] = l, 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);

	return pushup(x), x;

}

inline void dfs(int u, int f) {

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i]; if (v == f) continue;

		dfs(v, u), rt[u] = merge(rt[u], rt[v]);

	}

	update(rt[u], c[u]), ans[u] = col[rt[u]];

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n);

	for (rg int i = 1; i <= n; ++i) read(c[i]), rt[++cnt] = i;

	for (rg int u, v, i = 1; i < n; ++i)

		read(u), read(v), Add_edge(u, v), Add_edge(v, u);

	dfs(1, 0);

	for (rg int i = 1; i <= n; ++i) printf("%lld ", ans[i]);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「CF600E」Lomsat gelral

解题思路

细节注意事项

参考代码

最新文章

热门文章