比赛 树形数据结构进阶(再进阶) 评测结果 MMMMMMMTTTMTMMMMMMMM
题目名称 雨天的尾巴 最终得分 0
用户昵称 LikableP 运行时间 17.711 s
代码语言 C++ 内存使用 331.16 MiB
提交时间 2025-04-19 10:23:00
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <queue>
#define ls(root) root << 1
#define rs(root) root << 1 | 1
using namespace std;

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

struct ADD{
	int x, y, z;
} add[MAXM];

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

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

int euler[MAXN << 1], ecnt;
int appear[MAXN][3];
int depth[MAXN];
int grd[MAXN][17];

void dfs(int now, int fa) {
	euler[++ecnt] = now;
	appear[now][1] = ecnt;
	depth[now] = depth[fa] + 1;
	grd[now][0] = fa;
	for (int i = 1; i <= 16; ++i) {
		grd[now][i] = grd[grd[now][i - 1]][i - 1];
	}
	for (int i = head[now]; i; i = edge[i].next) {
		if (edge[i].v == fa) continue;
		dfs(edge[i].v, now);
	}
	euler[++ecnt] = now;
	appear[now][2] = ecnt;
}

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

struct NODE {
	unordered_map<int, int> food;
	queue <int> lazy;
	int maxf, maxx = -1;
} node[MAXN << 2];

void Update(int root, int x) {
	node[root].food[x] += 1;
	if (node[root].food[x] > node[root].maxx) {
		node[root].maxf = x;
		node[root].maxx = node[root].food[x];
	}
	node[root].lazy.push(x);
}

void PushDown(int root) {
	while (!node[root].lazy.empty()) {
		int x = node[root].lazy.front();
		node[root].lazy.pop();
		Update(ls(root), x);
		Update(rs(root), x);
	}
}

void AddSeq(int root, int lt, int rt, int lq, int rq, int x) {
	if (lt == rt && lq == rq) {
		Update(root, x);
		return ;
	}
	PushDown(root);
	int mid = lt + ((rt - lt) >> 1);
	if (rq <= mid) {
		AddSeq(ls(root), lt, mid, lq, rq, x);
	} else if (lq > mid) {
		AddSeq(rs(root), mid + 1, rt, lq, rq, x);
	} else {
		AddSeq(ls(root), lt, mid, lq, mid, x);
		AddSeq(rs(root), mid + 1, rt, mid + 1, rq, x);
	}
}

int Get(int root, int lt, int rt, int x) {
	if (lt == rt) {
		return node[root].maxf;
	}
	PushDown(root);
	int mid = lt + ((rt - lt) >> 1);
	if (x <= mid) {
		return Get(ls(root), lt, mid, x);
	} else {
		return Get(rs(root), mid + 1, rt, x);
	}
}

int n, m;
int b[MAXM], blen;

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 a, b;
		scanf("%d %d", &a, &b);
		AddEdge(a, b);
		AddEdge(b, a);
	}
	dfs(1, 0);;
	for (int i = 1; i <= m; ++i) {
		scanf("%d %d %d", &add[i].x, &add[i].y, &add[i].z);
		b[i] = add[i].z;
	}
	sort(b + 1, b + m + 1);
	blen = unique(b + 1, b + m + 1) - b - 1;
	for (int i = 1; i <= m; ++i) {
		int x = add[i].x, y = add[i].y, z = b[lower_bound(b + 1, b + blen + 1, 3) - b];
		int lca = LCA(x, y);
		if (lca == x || lca == y) {
			if (depth[x] < depth[y]) {
				AddSeq(1, 1, ecnt, appear[x][1], appear[y][1], z);
			} else {
				AddSeq(1, 1, ecnt, appear[y][1], appear[x][1], z);
			}
		} else {
			if (appear[x][1] < appear[y][1]) {
				AddSeq(1, 1, ecnt, appear[x][2], appear[y][1], z);
			} else {
				AddSeq(1, 1, ecnt, appear[y][2], appear[x][1], z);
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d\n", b[Get(1, 1, ecnt, appear[i][1])]);
	}
	return 0;
}