记录编号	600240	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	雨天的尾巴	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	4.064 s
提交时间	2025-04-22 21:47:10	内存使用	34.62 MiB

#include <cstdio>
#include <algorithm>

const int MAXN = 1e5 + 10;
const int MAXZ = 1e5;

struct EDGE {
	int v, next;
} edge[MAXN << 1];

int edgeNum, head[MAXN];
void AddEdge(int u, int v) {
	edge[++edgeNum].v = v;
	edge[edgeNum].next = head[u];
	head[u] = edgeNum;
}

struct NODE {
	int ls, rs;
	int maxx;
	int type;
} node[MAXN * 17 * 4];

void PushUp(int root) {
	if (node[node[root].ls].maxx >= node[node[root].rs].maxx) {
		node[root].maxx = node[node[root].ls].maxx;
		node[root].type = node[node[root].ls].type;
	} else {
		node[root].maxx = node[node[root].rs].maxx;
		node[root].type = node[node[root].rs].type;
	}
}

int nodeNum;
void AddSingle(int &root, int lt, int rt, int x, int val) {
	if (!root) root = ++nodeNum;
	if (lt == rt) {
		node[root].maxx += val;
		node[root].type = x;
		return ;
	}
	int mid = lt + ((rt - lt) >> 1);
	if (x <= mid) {
		AddSingle(node[root].ls, lt, mid, x, val);
	} else {
		AddSingle(node[root].rs, mid + 1, rt, x, val);
	}
	PushUp(root);
}

int grd[MAXN][20], depth[MAXN];
void dfs(int root, int fa) {
	depth[root] = depth[fa] + 1;
	grd[root][0] = fa;
	for (int i = 1; i <= 19; ++i) {
		grd[root][i] = grd[grd[root][i - 1]][i - 1];
	}
	for (int i = head[root]; i; i = edge[i].next) {
		if (edge[i].v == fa) continue;
		dfs(edge[i].v, root);
	}
}

int LCA(int x, int y) {
	if (depth[x] < depth[y]) {
		::std::swap(x, y);
	}
	for (int i = 19; i >= 0; --i) {
		if (depth[grd[x][i]] >= depth[y]) {
			x = grd[x][i];
		}
	}
	if (x == y) return x;
	for (int i = 19; i >= 0; --i) {
		if (grd[x][i] != grd[y][i]) {
			x = grd[x][i];
			y = grd[y][i];
		}
	}
	return grd[x][0];
}

int Merge(int x, int y, int lt, int rt) {
	if (!x || !y) return x + y;
	if (lt == rt) {
		node[x].maxx += node[y].maxx;
		return x;
	}
	int mid = lt + ((rt - lt) >> 1);
	node[x].ls = Merge(node[x].ls, node[y].ls, lt, mid);
	node[x].rs = Merge(node[x].rs, node[y].rs, mid + 1, rt);
	PushUp(x);
	return x;
}

int n, m; 
int root[MAXN];
int ans[MAXN];

void calc(int now, int fa) {
	for (int i = head[now]; i; i = edge[i].next) {
		if (edge[i].v == fa) continue;
		calc(edge[i].v, now);
		root[now] = Merge(root[now], root[edge[i].v], 1, MAXZ);
	}
	ans[now] = node[root[now]].maxx ? node[root[now]].type : 0;
}

int main() {
	freopen("Rainbows.in", "r", stdin);
	freopen("Rainbows.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n - 1; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		AddEdge(u, v);
		AddEdge(v, u);
	}
	dfs(1, 0);
	while (m--) {
		int x, y, z, lca;
		scanf("%d %d %d", &x, &y, &z);
		AddSingle(root[x], 1, MAXZ, z, 1);
		AddSingle(root[y], 1, MAXZ, z, 1);
		lca = LCA(x, y);
//		printf("([x]%d,[lca]%d) ([lca]%d,[x]%d)\n", x, lca, lca, x);
		AddSingle(root[lca], 1, MAXZ, z, -1);
		AddSingle(root[grd[lca][0]], 1, MAXZ, z, -1);
	}
	calc(1, 0);
	for (int i = 1; i <= n; ++i) {
		printf("%d\n", ans[i]);
	}
	return 0;
}