https://www.acwing.com/solution/content/57507/

上面是我的第一篇题解，我一直以为没有AC，空间复杂度太高是因为我用的是java

但是我用了Cpp之后才发现该优化的问题不出在java上，以下是已经AC的代码，主要是merge那一步进行了优化

我之前是每次merge都要开新的树，但是优化之后相当于在“不必要的情况下”不用开新的树

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N = 100010, M = 50* N;
int leftson[M], rightson[M], maximal[M], maxidx[M], root[N], cnt = 0;
int n, m;
// 上面这样做可以极大地节省空间复杂度
int father[N], son[N], howbig[N], top[N], timestamp = 0, depth[N], dfn[N], fi[N], ne[N << 1], en[N << 1], index = 0;
void add(int a, int b) {
    index++;
    ne[index] = fi[a];
    fi[a] = index;
    en[index] = b;
}
void dfs1(int u, int dad) {
    father[u] = dad;
    depth[u] = depth[dad] + 1;
    howbig[u] = 1;
    for (int p = fi[u]; p > 0; p = ne[p]) {
        int v = en[p];
        if (v == dad) continue;
        dfs1(v, u);
        howbig[u] += howbig[v];
        if (howbig[v] > howbig[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++timestamp;
    if (son[u]) dfs2(son[u], t);
    for (int p = fi[u]; p > 0; p = ne[p]) {
        int v = en[p];
        if (v == son[u] || v == father[u]) continue;
        dfs2(v, v);
    }
}
int lca(int a, int b) {
    while (top[a] != top[b]) {
        if (depth[top[a]] < depth[top[b]]) swap(a, b);
        a = father[top[a]];
    }
    if (depth[a] < depth[b]) return a;
    return b;
}
void pushup(int u) {
    int left = leftson[u], right = rightson[u];
    if (maximal[left] >= maximal[right]) maximal[u] = maximal[left], maxidx[u] = maxidx[left];
    else maximal[u] = maximal[right], maxidx[u] = maxidx[right];
}
void update(int u, int l, int r, int x, int c) {
    if (l == r) {
        maximal[u] += c; maxidx[u] = x;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        if (leftson[u] == 0) leftson[u] = ++cnt;
        update(leftson[u], l, mid, x, c);
    }
    else {
        if (rightson[u] == 0) rightson[u] = ++cnt;
        update(rightson[u], mid + 1, r, x, c);
    }
    pushup(u);
}
int b[N], t[N], len = 0;
struct Q {
    int x, y, z;
}op[N];
map<int, int> map1, map2;
void msort(int head, int tail) {
    if (head == tail) return;
    int mid = (head + tail) >> 1;
    msort(head, mid); msort(mid + 1, tail);
    int pointer1 = head, pointer2 = mid + 1;
    for (int i = 0; i < tail - head + 1; i++) {
        if (pointer1 <= mid && pointer2 <= tail) {
            if (b[pointer1] < b[pointer2]) t[i] = b[pointer1++];
            else t[i] = b[pointer2++];
        }
        else if (pointer1 <= mid) t[i] = b[pointer1++];
        else t[i] = b[pointer2++];
    }
    for (int i = 0; i < tail - head + 1; i++) b[i + head] = t[i];
}
void unique() {
    int cnt = 0;
    for (int i = 1; i <= len; i++) {
        if (map2.count(b[i]) != 0) continue;
        map2[b[i]] = ++cnt;
        map1[cnt] = b[i];
    }
    len = cnt;
}
int queue[N], head = 1, tail = 0;
void bfs() {
    queue[++tail] = 1;
    while (tail - head + 1 > 0) {
        int u = queue[head++];
        for (int p = fi[u]; p > 0; p = ne[p]) {
            int v = en[p];
            if (depth[v] != depth[u] + 1) continue;
            queue[++tail] = v;
        }
    }
}
void merge(int p, int q, int l, int r) {
    if (q == 0) return;
    if (l == r) {
        maximal[p] += maximal[q];
        maxidx[p] = l;
        return;
    }
    int mid = (l + r) >> 1;
    if (leftson[p] == 0 && leftson[q] != 0) {
        leftson[p] = leftson[q];
    }
    else if (leftson[p] != 0 && leftson[q] != 0) {
        merge(leftson[p], leftson[q], l, mid);
    }
    if (rightson[p] == 0 && rightson[q] != 0) {
        rightson[p] = rightson[q];
    }
    else if (rightson[p] != 0 && rightson[q] != 0) {
        merge(rightson[p], rightson[q], mid + 1, r);
    }
    pushup(p);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }
    dfs1(1, 0); dfs2(1, 1);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &op[i].x, &op[i].y, &op[i].z);
        b[++len] = op[i].z;
    }
    msort(1, len); unique();
    for (int i = 1; i <= m; i++) {
        int x = op[i].x, y = op[i].y, z = map2[op[i].z];
        int l = lca(x, y);
        if (root[x] == 0) root[x] = ++cnt;
        if (root[y] == 0) root[y] = ++cnt;
        if (root[l] == 0) root[l] = ++cnt;
        if (root[father[l]] == 0) root[father[l]] = ++cnt;
        update(root[x], 1, len, z, 1);
        update(root[y], 1, len, z, 1);
        update(root[l], 1, len, z, -1);
        update(root[father[l]], 1, len, z, -1);
    }
    bfs();
    for (int i = n; i >= 1; i--) {
        int u = queue[i];
        for (int p = fi[u]; p > 0; p = ne[p]) {
            int v = en[p];
            if (depth[v] != depth[u] + 1) continue;
            if (root[u] == 0) root[u] = ++cnt;
            merge(root[u], root[v], 1, len);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (maximal[root[i]] == 0) printf("%d\n", 0);
        else printf("%d\n", map1[maxidx[root[i]]]);
    }
}