I. content

Background of topic

Deep drawing has always hated rainy days.

The scorching weather penetrated the first half of the summer, and then a heavy rain and subsequent floods watered everything out.

Although the small village in shentuli's hometown has a stubborn resistance to the flood, several old houses have been collapsed, several old trees have been uprooted, and the food in the field has been made a mess.

But deep drawing and villagers had to wait for relief food to survive.

But the distribution of relief food is very special.

Title Description

First of all, there are nnn houses in the village, which form a tree structure. Then, the relief food is distributed in mmm times. Each time, two houses (x, y)(x,~y)(x, y) are selected. Then, a bag of zzz type relief food is distributed to each house on the route from xxx to yyy (including xxx and yyy).

Then I want to know what kind of relief food is stored most in each house after all the relief food is distributed.
Input format

The first line of input is two positive integers separated by spaces, which respectively represent the number of houses nnn and the number of relief food distribution mmm.

From line 222 to nnn, each line has two integers a, ba,~ba, b separated by spaces, representing that there is an edge connecting house aaa and house bbb.

From (n+1)(n + 1)(n+1) to (n+m)(n + m)(n+m), there are three integers x, y, zx,~y,~zx, y, z separated by spaces in each line, which means that each house on the route from xxx to yyy issues a bag of zzz type relief food.
Output format

The output nnn line is an integer in each line. The integer in line iii represents the type of relief food most stored in house iii. If there are multiple types of relief food, the output type number is the smallest.

If a house does not have relief food, 000 will be exported.

Input #1

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

Output #1

2
3
3
0
2

Two, train of thought

• Prefix knowledge: dynamic open point + line tree merging

• First of all, we have m types of relief grain at each point, and count the largest number of relief grain types. We can create a line segment tree at each point. The maximum value of 1~m type relief food stored in it.

• When we add relief food to the u-V path, we can use the difference on the tree

  • Each time, add 1 to z class of u line tree, 1 to z class of v line tree, 1 to z class of lca, and - 1 to parent node of lca. In this way, the number of each relief grain with u > v is differentiated.

• In the last dfs, only the line segment trees of two points need to be merged. In this way, the largest of each type is merged into a point.
  

Three, code

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
struct Node {
	int lc, rc, mx, id; //mx save Max id save its number 
} tr[N * 80];
struct E {int v, next;} e[N << 1];
int n, m, u[N], v[N], z[N], idz[N], cntz, lg, len, cnt, h[N], f[N][18], dep[N], rt[N], ans[N]; //cnt is the number of dynamic open points rt represents the root node number of the segment tree of each node 
void add(int u, int v) {e[++len].v = v; e[len].next = h[u]; h[u] = len;}
void bfs() {
	dep[1] = 1; queue<int> q; q.push(1); 
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int j = h[u]; j; j = e[j].next) {
			int v = e[j].v;
			if (dep[v]) continue;
			dep[v] = dep[u] + 1;
			q.push(v); f[v][0] = u;
			for (int k = 1; k <= lg; k++) f[v][k] = f[f[v][k - 1]][k - 1];
		}
 	}
}
int LCA(int x, int y) {
	if (dep[y] > dep[x]) swap(x, y);
	for (int k = lg; k >= 0; k--) {
		if (dep[f[x][k]] >= dep[y]) x = f[x][k];
	}
	if (x == y) return x;
	for (int k = lg; k >= 0; k--) {
		if (f[x][k] != f[y][k]) x = f[x][k], y = f[y][k];
	}
	return f[x][0];
}
void pushup(int id) {
	int lc = tr[id].lc, rc = tr[id].rc;
	//The number of the left section must be smaller than that of the right section, so when the remedies are equal, the left section number is stored 
	if (tr[lc].mx >= tr[rc].mx) tr[id].mx = tr[lc].mx, tr[id].id = tr[lc].id;
	else tr[id].mx = tr[rc].mx, tr[id].id = tr[rc].id; 
}
void update(int &id, int l, int r, int x, int c) {
	if (!id) id = ++cnt; //Dynamic point building
	if (l == r) {
		tr[id].mx += c;	tr[id].id = l;
		return;
	} 
	int mid = (l + r) >> 1;
	if (x <= mid) update(tr[id].lc, l, mid, x, c);
	else update(tr[id].rc, mid + 1, r, x, c);
	pushup(id);
}
int merge(int p, int q, int l, int r) {
	if (!p) return q; if (!q) return p;
	if (l == r) {
		tr[p].mx += tr[q].mx;
		return p;
	}
	int mid = (l + r) >> 1;
	tr[p].lc = merge(tr[p].lc, tr[q].lc, l, mid);
	tr[p].rc = merge(tr[p].rc, tr[q].rc, mid + 1, r);
	pushup(p);
	return p;
}
void dfs(int u, int fa) {
	for (int j = h[u]; j; j = e[j].next) {
		int v = e[j].v;
		if (v == fa) continue;
		dfs(v, u);
		rt[u] = merge(rt[u], rt[v], 1, cntz);
	}
	ans[u] = tr[rt[u]].mx == 0 ? 0 : tr[rt[u]].id;
}
int main() {
	scanf("%d%d", &n, &m);
	lg = int(log(n) / log(2)) + 1;
	for (int i = 1; i < n; i++) {
		scanf("%d%d", &u[0], &v[0]);
		add(u[0], v[0]); add(v[0], u[0]);
	}	
	bfs();
	for (int i = 1; i <= m; i++) { scanf("%d%d%d", &u[i], &v[i], &z[i]); idz[i] = z[i];}
	//Discretization of z
	sort(idz + 1, idz + 1 + m);
	cntz = unique(idz + 1, idz + 1 + m) - idz - 1;
	for (int i = 1; i <= m; i++) {
		int lca = LCA(u[i], v[i]);
		int zt = lower_bound(idz + 1, idz + 1 + cntz, z[i]) - idz;
		update(rt[u[i]], 1, cntz, zt, 1);
		update(rt[v[i]], 1, cntz, zt, 1);
		update(rt[lca], 1, cntz, zt, -1);
		update(rt[f[lca][0]], 1, cntz, zt, -1);		
	} 
	dfs(1, 0);
	for (int i = 1; i <= n; i++) printf("%d\n", idz[ans[i]]);
	return 0;
}