线段树合并, 80 分, 并不知道出了什么锅 /kel

#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define ll long long
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 6000005
struct node {
	int l, r, val, id;
} tr[_] ; int tot;
inline int& newNode() { return ++tot; }
inline int& ls(int x) { return tr[x].l; }
inline int& rs(int x) { return tr[x].r; }
inline int& val(int x) { return tr[x].val; }
inline int& id(int x) { return tr[x].id; }
inline void pushup(int p) {
	if(val(ls(p))>val(rs(p))) { val(p)=val(ls(p)); id(p)=id(ls(p)); }
	else if(val(ls(p))<val(rs(p))) { val(p)=val(rs(p)); id(p)=id(rs(p)); }
	else { val(p)=val(ls(p)); id(p)=min(id(ls(p)), id(rs(p))); }
}
void modify(int p, int l, int r, int q, int x) {
	if(l==r) { id(p)=l; val(p)+=x; return ; }
	int mid=(l+r)>>1;
	if(q<=mid) {
		ls(p) = ls(p) ? ls(p) : newNode();
		modify(ls(p), l, mid, q, x);
	} else {
		rs(p) = rs(p) ? rs(p) : newNode();
		modify(rs(p), mid+1, r, q, x);
	}
	pushup(p);
}
pair<int, int> max(pair<int, int> x, pair<int, int> y) {
	return (x.first == y.first) ? ((x.second < y.second) ? (x) : (y)) : ((x.first < y.first) ? (y) : (x));
}
pair<int, int> query(int p, int l, int r, int ql, int qr) {
	if(ql<=l && r<=qr) return make_pair(val(p), id(p));
	int mid=(l+r)>>1; auto res=make_pair(-1, 0);
	if(ql<=mid) res=max(res, query(ls(p), l, mid, ql, qr));
	if(qr>mid) res=max(res, query(rs(p), mid+1, r, ql, qr));
	return res;
}
int rt[_], n, m;
vector<int> edge[_]; int fa[_][20], dep[_];
void add(int u, int v) {
	edge[u].push_back(v);
}
void dfs(int f, int u, int d) {
	// printf("dfs: at %d\n", u);
	fa[u][0]=f; dep[u]=d;
	for(auto& x:edge[u]) if(x!=f) dfs(u, x, d+1);
}
void init() {
	f(T,1,19) f(i,1,n) fa[i][T]=fa[fa[i][T-1]][T-1];
	//printf("fa[%d][%d]=%d\n", 5, 1, fa[5][1]);
}
int lca(int x, int y) {
	if(x==y) return x;
	if(dep[x]<dep[y]) swap(x, y);
	d(i,0,19) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	//printf("x=%d, y=%d\n", x, y);
	if(x==y) return x;
	d(i,0,19) if(fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
	return fa[x][0];
}
const int color=1e5; int ans[_];
int merge(int p, int q, int l, int r) {
	if(!p||!q) return p+q;
	if(l==r) { val(p)+=val(q); id(p)=l; return p; }
	int mid=(l+r)>>1;
	ls(p) = merge(ls(p), ls(q), l, mid);
	rs(p) = merge(rs(p), rs(q), mid+1, r);
	pushup(p); return p;
}
void printTree(int p, int l, int r) {
	//printf("Node[%d] = (ls=%d, rs=%d, val=%d, id=%d)\n", p, ls(p), rs(p), val(p), id(p));
	int mid=(l+r)>>1;
	if(ls(p)) printTree(ls(p), l, mid);
	if(rs(p)) printTree(rs(p), mid+1, r);
}
void solve(int f, int u) {
	//printf("PrintTree : %d\n", u); printTree(rt[u], 1, color);
	for(auto& x:edge[u]) if(x!=f) { solve(u, x); merge(rt[u], rt[x], 1, color); /*printf("PrintTree : %d\n", u); printTree(rt[u], 1, color);*/ }
	auto res=query(rt[u], 1, color, 1, color);
	//printf("ans[%d]=(%d, %d)\n", u, res.first, res.second);
	ans[u]=res.first > 0 ? res.second : 0 ;
}
int main() {
	//auto p=make_pair(1, 3), q=make_pair(2, 4);
	//p=max(p, q); printf("p=(%d, %d)\n", p.first, p.second);
	rd(n); rd(m);
	int x, y, z; f(i,2,n) { rd(x); rd(y); add(x, y); add(y, x); }
  dfs(0, 1, 0); init(); f(i,1,n) rt[i]=newNode();
	//printf("%d\n", lca(1, 5));
	f(i,1,m) {
		rd(x); rd(y); rd(z);
		modify(rt[x], 1, color, z, 1);
		modify(rt[y], 1, color, z, 1);
		modify(rt[lca(x, y)], 1, color, z, -1); //printf("Modify(-1) : (%d, %d)\n", lca(x,y), z);
		if(fa[lca(x, y)][0] != 0) { modify(rt[fa[lca(x, y)][0]], 1, color, z, -1); /*printf("Modify(-1) : (%d, %d)\n", fa[lca(x,y)][0], z);*/ }
	}
	solve(-1, 1);
	f(i,1,n) printf("%d%c", ans[i], "\n\n"[i==n]);
  return 0;
}