luoguP4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并（线段树-权值-动态开点，树链剖分）

中学毕业了，十七号就要前往武汉报道。中学的终点是武汉大学，人生的终点却不是，最初的热情依然失却，我还是回来看看这分类排版皆惨淡的博客吧，只是是用来保存代码也好。想要换一个新博客，带着之前的经验能把它整理得更好。就如人生总渴求一个新的开始，却往往是在过去的殷墟间孑孓独行。既然如此，暂且继续用这个博客吧。中学时的OI结局是我多年来的遗憾，这可能也是支持我果断参加ACM并用整个假期参与多校训练赛的本心吧。我从不相信天才，那只是兴趣遇上合适教育与一点幸运的人，都是一样的。然而，多年来也意识到自己匮乏的天分与耽误的时光，不由想到刚起程的ACM也可能以新的遗憾收尾。可是，不走下去，又怎能见证一路的风景？我不是个积极的人，所以需要一个方向指引我，只是回忆路边的景致就令我沉醉。我刚开始的时候，DEV连c++11都不支持，而现在，我习惯了用C++20，所以，多少是有点改变的，是吧？过去的憧憬，如今的理性，像两颗枝蔓不断衍生的线段树，就这样合并起来。把路上的一切剖分，锁定每个节点对应的色彩，又一点点开出新的节点，一路上，差分，合并，统计，便是答案

# include "bits/stdc++.h"

using namespace std;

constexpr int N = 1e5 + 3;

int main() {

	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	int n, m;

	cin >> n >> m;

	vector G(n + 1, vector<int>());

	for(int i = 1; i < n; ++i) {

		int u, v;

		cin >> u >> v;

		G[u].push_back(v);

		G[v].push_back(u);

	}

	vector<int> fa(n + 1), siz(n + 1), dep(n + 1), son(n + 1, 0);

	dep[0] = 0;

	auto dfs_first = [&](auto dfs_first, int u, int father) -> void {

		fa[u] = father, siz[u] = 1, dep[u] = dep[father] + 1;

		for(auto v : G[u]) {

			if(v == father) continue;

			dfs_first(dfs_first, v, u);

			siz[u] += siz[v];

			if(siz[son[u]] < siz[v]) son[u] = v;

		}

	};

	dfs_first(dfs_first, 1, 0);

	vector<int> top(n + 1);

	auto dfs_second = [&](auto dfs_second, int u, int ancestor) -> void {

		top[u] = ancestor;

		if(!son[u]) return;

		dfs_second(dfs_second, son[u], ancestor);

		for(auto v : G[u]) {

			if(son[u] != v && fa[u] != v) {

				dfs_second(dfs_second, v, v);

			}

		}

	};

	dfs_second(dfs_second, 1, 1);

	struct node {

		int l, r, id, val; // id -> color

	} t[N << 6]; // weight segment tree : for each color, build a tree

	vector<int> rt(n + 1, 0);

	int tree_index = 0;

	# define ls t[rt].l

	# define rs t[rt].r

	# define lson t[rt].l, l, mid

	# define rson t[rt].r, mid + 1, r

	auto push_up = [&](int rt) -> void {

		if(t[ls].val < t[rs].val) { // if the same, output the smaller color-index

			t[rt].val = t[rs].val;

			t[rt].id = t[rs].id;

		}

		else {

			t[rt].val = t[ls].val;

			t[rt].id = t[ls].id; // id -> color

		}

	};

	vector<int> ans(n + 1, 0);

	while(m--) {

		int x, y, col;

		cin >> x >> y >> col;

		auto LCA = [&](int x, int y) -> int {

			while(top[x] != top[y]) {

				if(dep[top[x]] < dep[top[y]]) x ^= y ^= x ^= y;

				x = fa[top[x]];

			}

			return dep[x] < dep[y] ? x : y;

		};

		int lca = LCA(x, y);

		auto update = [&](auto update, int &rt, int l, int r, int col, int val) -> void {

			if(!rt) rt = ++tree_index;

			if(l == r) {

				t[rt].val += val;

				t[rt].id = col;

				return;

			}

			int mid = l + r >> 1;

			if(col <= mid)

				update(update, lson, col, val);

			else

				update(update, rson, col, val);

			push_up(rt);

		};

		update(update, rt[x], 1, N - 1, col, 1);

		update(update, rt[y], 1, N - 1, col, 1);

		update(update, rt[lca], 1, N - 1, col, -1);

		if(lca != 1) update(update, rt[fa[lca]], 1, N - 1, col, -1);

	}

	auto merge = [&](auto merge, int x, int y, int l, int r) -> int { // x, y -> different segment tree

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

		if(l == r) { // l == r -> (x, y -> same color node)

			t[x].val += t[y].val;

			return x;

		}

		int mid = l + r >> 1;

		t[x].l = merge(merge, t[x].l, t[y].l, l, mid);

		t[x].r = merge(merge, t[x].r, t[y].r, mid + 1, r);

		push_up(x);

		return x;

	};

	auto dfs = [&](auto dfs, int u, int father) -> void {

		for(auto v : G[u]) {

			if(v == father) continue;

			dfs(dfs, v, u);

			rt[u] = merge(merge, rt[u], rt[v], 1, N - 1);

		}

		if(t[rt[u]].val) {

			ans[u] = t[rt[u]].id;

		}

	};

	dfs(dfs, 1, 0);

	for(int i = 1; i <= n; ++i) cout << ans[i] << "\n"[i == n];

	return 0;

}

巴特西

luoguP4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并（线段树-权值-动态开点，树链剖分）

最新文章

热门文章

巴特西

luoguP4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 （线段树-权值-动态开点，树链剖分）

最新文章

热门文章

luoguP4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并（线段树-权值-动态开点，树链剖分）