思路

好恶心的卡常题(虽然一边颓废一边写,还是卡了一下午).
如果空间和时间足够大,我们可以考虑对每一种粮食开一个大小的数组,若某条路径放类型的粮食,,树上前缀和,然后找出最大值即可.不过这样就算是离散化后,时空复杂度都是.
不过这样直接把开的数组改成动态开点线段树就好了.求前缀和的过程可以看成线段树合并.由于空间不是很足(主要是洛谷,牛客网给的内存海星,但是时间就...),因此需要对颜色进行离散化.时间复杂度为.
然后只要注意常数问题就OK.("只要"?)

代码

#include<cstdio>
#include<algorithm>
using namespace std;
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void read( T &x ){
    char t(getchar()), flg(0); x = 0;
    for ( ; t > 57 || t < 48; t = getchar() ) flg = t == '-';
    for ( ; 47 < t && t < 58; t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}

const int MAXN = 1e5 + 5, MAX = MAXN * 16 * 4;
int N, M, m, b[MAXN], _x[MAXN], _y[MAXN], _z[MAXN];
int T[MAXN], s[MAX], p[MAX], ls[MAX], rs[MAX], cnt;
int hd[MAXN], nxt[MAXN<<1], to[MAXN<<1], tot;
int dep[MAXN], f[MAXN][17];

inline void addedge( int x, int y ){
    nxt[++tot] = hd[x], hd[x] = tot, to[tot] = y,
    nxt[++tot] = hd[y], hd[y] = tot, to[tot] = x;
} void DFS( int u ){
    dep[u] = dep[f[u][0]] + 1;
    fp( i, 1, 16 ) f[u][i] = f[f[u][i - 1]][i - 1];
    go( i, hd[u] ) if ( v != f[u][0] )
        f[v][0] = u, DFS(v);
} inline int LCA( int x, int y ){
    if ( dep[x] < dep[y] ) x^=y^=x^=y;
    fd( i, 16, 0 ) if ( dep[f[x][i]] > dep[y] ) x = f[x][i];
    if ( dep[x] > dep[y] ) x = f[x][0];
    fd( i, 16, 0 ) if ( f[x][i] != f[y][i] ) x = f[x][i], y = f[y][i];
    return x != y ? f[x][0] : x;
} void Add( int &c, int l, int r, int w, int d ){
    if ( !c ) c = ++cnt;
    if ( l == r ) return s[c] += d, p[c] = l, void();
    int mid((l + r) >> 1);
    if ( w <= mid ) Add( ls[c], l, mid, w, d );
    else Add( rs[c], mid + 1, r, w, d );
    if ( !rs[c] || s[ls[c]] >= s[rs[c]] ) s[c] = s[ls[c]], p[c] = p[ls[c]];
    else s[c] = s[rs[c]], p[c] = p[rs[c]];
} void Merge( int &c, int o, int l, int r ){
    if ( !o ) return;
    if ( !c ) return c = o, void();
    if ( l == r ) return s[c] += s[o], void();
    int mid((l + r) >> 1);
    Merge( ls[c], ls[o], l, mid ), Merge( rs[c], rs[o], mid + 1, r );
    if ( !rs[c] || s[ls[c]] >= s[rs[c]] ) s[c] = s[ls[c]], p[c] = p[ls[c]];
    else s[c] = s[rs[c]], p[c] = p[rs[c]];
} int ans[MAXN];
void dfs( int u ){
    go( i, hd[u] ) if ( v != f[u][0] )
        dfs(v), Merge( T[u], T[v], 1, m );
    if ( s[T[u]] ) ans[u] = b[p[T[u]]];
}

int main(){
    read(N), read(M); int x, y;
    fp( i, 1, N - 1 ) read(x), read(y), addedge(x, y);
    fp( i, 1, M ) read(_x[i]), read(_y[i]), read(_z[i]), b[i] = _z[i];
    sort( b + 1, b + M + 1 ), m = unique( b + 1, b + M + 1 ) - b - 1;    
    DFS(1);
    fp( i, 1, M ){
        int t(LCA(_x[i], _y[i])), p(lower_bound( b + 1, b + m + 1, _z[i] ) - b);
        Add( T[_x[i]], 1, m, p, 1 );
        Add( T[_y[i]], 1, m, p, 1 );
        Add( T[t], 1, m, p, -1 );
        if ( f[t][0] ) Add( T[f[t][0]], 1, m, p, -1 );
    }
    dfs(1); fp( i, 1, N ) printf( "%d\n", ans[i] );
    return 0;
}