比赛 |
树形数据结构进阶(再进阶) |
评测结果 |
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;
}