[Vani有约会]雨天的尾巴 /【模板】线段树合并

题目背景

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

题目描述

首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x, y)\)，然后对于 \(x\) 到 \(y\) 的路径上（含 \(x\) 和 \(y\)）每座房子里发放一袋 \(z\) 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

输入格式

输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数 \(n\) 和救济粮发放的次数 \(m\)。

第 \(2\) 到 第 \(n\) 行，每行有两个用空格隔开的整数 \(a, b\)，代表存在一条连接房屋 \(a\) 和 \(b\) 的边。

第 \((n + 1)\) 到第 \((n + m)\) 行，每行有三个用空格隔开的整数 \(x, y, z\)，代表一次救济粮的发放是从 \(x\) 到 \(y\) 路径上的每栋房子发放了一袋 \(z\) 类型的救济粮。

输出格式

输出 \(n\) 行，每行一个整数，第 \(i\) 行的整数代表 \(i\) 号房屋存放最多的救济粮的种类，如果有多种救济粮都是存放最多的，输出种类编号最小的一种。

如果某座房屋没有救济粮，则输出 \(0\)。

样例 #1

样例输入 #1

5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3

样例输出 #1

2
3
3
0
2

提示

• 对于 \(20\%\) 的数据，保证 \(n, m \leq 100\)。
• 对于 \(50\%\) 的数据，保证 \(n, m \leq 2 \times 10^3\)。
• 对于 \(100\%\) 测试数据，保证 \(1 \leq n, m \leq 10^5\)，\(1 \leq a,b,x,y \leq n\)，\(1 \leq z \leq 10^5\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define lid (tree[id].lson)
#define rid (tree[id].rson)

using namespace std;

int n, m;
int cnt, head[5211314], nex[5211314], to[5211314];
int rank_[5211314], new_id;
int root[5211314];
int out[5211314];

struct Heavy_Light_Tree {
	int deep;
	int father;
	int son;
	int id;
	int size;
	int top;
}htree[5211314];

struct Segment_Tree {
	int lson, rson;
	int maxn, color;
}tree[52113140];

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch - '0');
		ch = getchar();
	}
	return f * x;
}

inline void AddPoi(int v1, int v2) {
	++ cnt;
	nex[cnt] = head[v1];
	head[v1] = cnt;
	to[cnt] = v2;
	return;
}

void DfsSon(int now, int father) {
	htree[now].deep = htree[father].deep + 1;
	htree[now].father = father;
	htree[now].size = 1;
	for (int i = head[now]; i != 0; i = nex[i]) {
		if (to[i] == father) continue;
		DfsSon(to[i], now);
		htree[now].size += htree[to[i]].size;
		if (htree[to[i]].size > htree[htree[now].son].size) {
			htree[now].son = to[i];
		}
	}
	return;
}

void DfsTop(int now, int top) {
	htree[now].top = top;
	if (htree[now].son != 0) DfsTop(htree[now].son, top);
	for (int i = head[now]; i != 0; i =nex[i]) {
		if (to[i] != htree[now].father && to[i] != htree[now].son) {
			DfsTop(to[i], to[i]);
		}
	}
	return;
}

inline int LCA(int x, int y) {
	while (htree[x].top != htree[y].top) {
		if (htree[htree[x].top].deep < htree[htree[y].top].deep) swap(x, y);
		x = htree[htree[x].top].father;
	}
	if (htree[x].deep > htree[y].deep) swap(x, y);
	return x;
}

class Segment {
	private:
		void Pushup(int id) {
			if (tree[lid].maxn < tree[rid].maxn) {
				tree[id].maxn = tree[rid].maxn;
				tree[id].color = tree[rid].color;
			}
			else {
				tree[id].maxn = tree[lid].maxn;
				tree[id].color = tree[lid].color;
			}
		}
	public:
		int Update(int id, int l, int r, int color, int number) {
			//单点更新 
			if (id == 0) id = ++ cnt;
			if (l == r) {
				tree[id].maxn += number;
				tree[id].color = color;
				return id;
			}
			int mid = (l + r) >> 1;
			if (color <= mid) lid = Update(lid, l, mid, color, number);
			else rid = Update(rid, mid + 1, r, color, number);
			Pushup(id);
			return id;
		}
		int Merge(int a, int b, int l, int r) {
			if (a == 0) return b;
			if (b == 0) return a;			
			// 返回非空树  
			if (l == r) {
				tree[a].maxn += tree[b].maxn;
				return a;
			}
			int mid = (l + r) >> 1;
			tree[a].lson = Merge(tree[a].lson, tree[b].lson, l, mid);
			tree[a].rson = Merge(tree[a].rson, tree[b].rson, mid + 1, r);
			Pushup(a);
			return a;
		}
}ask;

void operate(int now) {
	for (int i = head[now]; i != 0; i = nex[i]) {
		if (to[i] == htree[now].father) continue;
		operate(to[i]);
		root[now] = ask.Merge(root[now], root[to[i]], 1, 100000); 
	}
	if (tree[root[now]].maxn == 0) out[now] = 0;
	else out[now] = tree[root[now]].color;
	return;
}

int main() {
	n = read();
	m = read();
	for (int i = 1, a, b; i <= n - 1; ++ i) {
		a = read();
		b = read();
		AddPoi(a, b);
		AddPoi(b, a);
	}
	DfsSon(1, 0);
	DfsTop(1, 1);
	for (int i = 1, x, y, z, lca; i <= m; ++ i) {
		x = read();
		y = read();
		z = read();
		root[x] = ask.Update(root[x], 1, 100000, z, 1);
		root[y] = ask.Update(root[y], 1, 100000, z, 1);
		//树上差分 树上查询的两点的值+1，两点间的lca的值-1，lca的fa的值减一
		//         每个节点表示被经过几次 
		lca = LCA(x, y);
		root[lca] = ask.Update(root[lca], 1, 100000, z, -1);
		root[htree[lca].father] = ask.Update(root[htree[lca].father], 1, 100000, z, -1);
	}
	operate(1);
	for (int i = 1; i <= n; ++ i) {
		printf("%d\n", out[i]);
	}
	return 0;
}