嘟嘟嘟
看到链上操作，自然想到树剖。
先考虑序列上的问题：那么区间修改可以用差分。所以我们把操作拆成(L)和(R + 1)两个点，然后离线。排序后扫一遍，用线段树维护数量最多的颜色是哪一个。
现在改成了树上，那么就用树剖把链变成一段段区间，然后做法和上面就一样了。
复杂度(O(n ^ 2logn))。
（据说这题还有线段树合并的做法，但是我没想出来）
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
const int maxq = 4e6 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m;
struct Edge
{
int nxt, to;
}e[maxn << 1];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
int dep[maxn], siz[maxn], son[maxn], fa[maxn];
In void dfs1(int now, int _f)
{
siz[now] = 1;
for(int i = head[now], v; ~i; i = e[i].nxt)
{
if((v = e[i].to) == _f) continue;
dep[v] = dep[now] + 1;
fa[v] = now;
dfs1(v, now);
siz[now] += siz[v];
if(!son[now] || siz[son[now]] < siz[v]) son[now] = v;
}
}
int dfsx[maxn], pos[maxn], top[maxn], cnt = 0;
In void dfs2(int now, int _f)
{
dfsx[now] = ++cnt; pos[cnt] = now;
if(son[now]) top[son[now]] = top[now], dfs2(son[now], now);
for(int i = head[now], v; ~i; i = e[i].nxt)
{
if((v = e[i].to) == _f || v == son[now]) continue;
top[v] = v, dfs2(v, now);
}
}
struct Node
{
int id, flg, col;
In bool operator < (const Node& oth)const
{
return id < oth.id;
}
}q[maxq];
int qcnt = 0;
In void solve(int x, int y, int col)
{
while(top[x] ^ top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
q[++qcnt] = (Node){dfsx[top[x]], 1, col};
q[++qcnt] = (Node){dfsx[x] + 1, -1, col};
x = fa[top[x]];
}
if(dfsx[x] < dfsx[y]) swap(x, y);
q[++qcnt] = (Node){dfsx[y], 1, col};
q[++qcnt] = (Node){dfsx[x] + 1, -1, col};
}
int Max_col;
int l[maxn << 2], r[maxn << 2], Max[maxn << 2], Mpos[maxn << 2];
In void build(int L, int R, int now)
{
l[now] = L; r[now] = R;
if(L == R) {Mpos[now] = L; return;}
int mid = (L + R) >> 1;
build(L, mid, now << 1);
build(mid + 1, R, now << 1 | 1);
Mpos[now] = Mpos[now << 1];
}
In void update(int id, int now, int d)
{
if(l[now] == r[now]) {Max[now] += d; return;}
int mid = (l[now] + r[now]) >> 1;
if(id <= mid) update(id, now << 1, d);
else update(id, now << 1 | 1, d);
if(Max[now << 1] >= Max[now << 1 | 1]) Max[now] = Max[now << 1], Mpos[now] = Mpos[now << 1];
else Max[now] = Max[now << 1 | 1], Mpos[now] = Mpos[now << 1 | 1];
}
int ans[maxn];
int main()
{
Mem(head, -1);
n = read(), m = read();
for(int i = 1; i < n; ++i)
{
int x = read(), y = read();
addEdge(x, y), addEdge(y, x);
}
dfs1(1, 0); top[1] = 1, dfs2(1, 0);
for(int i = 1; i <= m; ++i)
{
int x = read(), y = read(), col = read();
Max_col = max(Max_col, col);
solve(x, y, col);
}
sort(q + 1, q + qcnt + 1);
build(0, Max_col, 1);
for(int i = 1, j = 1; i <= cnt; ++i)
{
while(q[j].id == i) update(q[j].col, 1, q[j].flg), ++j;
ans[pos[i]] = Mpos[1];
}
for(int i = 1; i <= n; ++i) write(ans[i]), enter;
return 0;
}