rt，其他操作完全一致，但用 vector 存图，可以水过，但用链式前向星存图会 T。

注意到两条记录的用时差了接近一倍，有点难以理解，有人能解释一下为什么吗……

这是用 vector 存图的代码：

#include<iostream>
#include<cstring>
#include<vector>
#define skip(x) x=anc[x][i]
#define rep for(int v:e[u])
#define handle if(v==f)continue;
#define down for(int i=20;i>=0;--i)
#define init anc[u][0]=f;d[u]=d[f]+1;
using namespace std;

const int N=1e5+5;
const int Z=1e5;

int n,m,cnt;
int d[N],maxx[N*60],ans[N],id[N*60];
int ls[N*60],rs[N*60],root[N];
int anc[N][25];
vector<int> e[N];

inline void dfsA(int u,int f){
	init;
	for(int i=1;i<=20;++i){
		anc[u][i]=anc[anc[u][i-1]][i-1];
	}
	rep{
		handle;
		dfsA(v,u);
	}
	return ;
}

inline int LCA(int x,int y){
	if(d[x]<d[y])swap(x,y);
	down{
		if(d[anc[x][i]]>=d[y]){
			skip(x);
		}
	}
	if(x==y)return x;
	down{
		if(anc[x][i]==anc[y][i])continue;
		skip(x),skip(y);
	}
	return anc[x][0];
}

inline void pushup(int u){
	maxx[u]=maxx[ls[u]]>=maxx[rs[u]]?maxx[ls[u]]:maxx[rs[u]];
	id[u]=maxx[ls[u]]>=maxx[rs[u]]?id[ls[u]]:id[rs[u]];
	return ;
}

inline void update(int &u/*当前结点号*/,int l/*左端点*/,int r/*右端点*/,int x/*目标*/,int v/*1 或 -1*/){
	if(u==0)u=++cnt;
	if(l==r){
		maxx[u]+=v;
		id[u]=x;
		return ;
	}
	int mid=(l+r)/2;
	if(x<=mid)update(ls[u],l,mid,x,v);
	else update(rs[u],mid+1,r,x,v);
	pushup(u);
	return ;
}

inline int merge(int u,int v,int l,int r){
	if(u==0||v==0)return u==0?v:u;
	if(l==r){
		maxx[u]+=maxx[v];
		id[u]=l;
		return u;
	}
	int mid=(l+r)/2;
	ls[u]=merge(ls[u],ls[v],l,mid);
	rs[u]=merge(rs[u],rs[v],mid+1,r);
	pushup(u);
	return u;
}

inline void dfsB(int u,int f){
	rep{
		handle;
		dfsB(v,u);
		root[u]=merge(root[u],root[v],1,Z);
	}
	ans[u]=maxx[root[u]]?id[root[u]]:0;
	return ;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<n;++i){
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfsA(1,0);
	for(int i=1;i<=m;++i){
		int x,y,z;
		cin>>x>>y>>z;
		int lca=LCA(x,y);
		update(root[x],1,Z,z,1);
		update(root[y],1,Z,z,1);
		update(root[lca],1,Z,z,-1);
		if(anc[lca][0])update(root[anc[lca][0]],1,Z,z,-1);
	}
	dfsB(1,0);
	for(int i=1;i<=n;++i)cout<<ans[i]<<"\n";
	return 0;
}

而这是用链式前向星存图的代码（甚至还卡了常：

#include<cstdio>
#define skip(x) x=anc[x][i]
#define rep for(int i=head[u];i;i=e[i].nxt)
#define handle int v=e[i].v;if(v==f)continue;
#define down for(int i=20;i>=0;--i)
#define init anc[u][0]=f;d[u]=d[f]+1;
using namespace std;

namespace OIfast{
	
	inline int read(){
		int n=0,f=1;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-')f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
		return n*f;
	}
	
	inline void print(int n){
		if(n<0)n=-n,putchar('-');
		if(n>=10)print(n/10);
		putchar(n%10+'0');
		return ;
	}
	
	inline void write(int n,char c){
		print(n),putchar(c);
		return ;
	}
	
}using namespace OIfast;

const int N=1e5+5;
const int Z=1e5;

int n,m,cnt,tot;
int head[N],d[N],maxx[N*60],ans[N],id[N*60];
int ls[N*60],rs[N*60],root[N];
int anc[N][25];

struct edge{
	int v,nxt;
}e[N];

inline void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
	return ;
}

inline void dfsA(int u,int f){
	init;
	for(int i=1;i<=20;++i){
		anc[u][i]=anc[anc[u][i-1]][i-1];
	}
	rep{
		handle;
		dfsA(v,u);
	}
	return ;
}

inline int LCA(int x,int y){
	if(d[x]<d[y])x^=y,y^=x,x^=y;
	down{
		if(d[anc[x][i]]>=d[y]){
			skip(x);
		}
	}
	if(x==y)return x;
	down{
		if(anc[x][i]==anc[y][i])continue;
		skip(x),skip(y);
	}
	return anc[x][0];
}

inline void pushup(int u){
	maxx[u]=maxx[ls[u]]>=maxx[rs[u]]?maxx[ls[u]]:maxx[rs[u]];
	id[u]=maxx[ls[u]]>=maxx[rs[u]]?id[ls[u]]:id[rs[u]];
	return ;
}

inline void update(int &u/*当前结点号*/,int l/*左端点*/,int r/*右端点*/,int x/*目标*/,int v/*1 或 -1*/){
	if(u==0)u=++cnt;
	if(l==r){
		maxx[u]+=v;
		id[u]=x;
		return ;
	}
	int mid=(l+r)/2;
	if(x<=mid)update(ls[u],l,mid,x,v);
	else update(rs[u],mid+1,r,x,v);
	pushup(u);
	return ;
}

inline int merge(int u,int v,int l,int r){
	if(u==0||v==0)return u==0?v:u;
	if(l==r){
		maxx[u]+=maxx[v];
		id[u]=l;
		return u;
	}
	int mid=(l+r)/2;
	ls[u]=merge(ls[u],ls[v],l,mid);
	rs[u]=merge(rs[u],rs[v],mid+1,r);
	pushup(u);
	return u;
}

inline void dfsB(int u,int f){
	rep{
		handle;
		dfsB(v,u);
		root[u]=merge(root[u],root[v],1,Z);
	}
	ans[u]=maxx[root[u]]?id[root[u]]:0;
	return ;
}

signed main(){
	n=read(),m=read();
	for(int i=1;i<n;++i){
		int a=read(),b=read();
		add(a,b);
		add(b,a);
	}
	dfsA(1,0);
	for(int i=1;i<=m;++i){
		int x=read(),y=read(),z=read();
		int lca=LCA(x,y);
		update(root[x],1,Z,z,1);
		update(root[y],1,Z,z,1);
		update(root[lca],1,Z,z,-1);
		if(anc[lca][0])update(root[anc[lca][0]],1,Z,z,-1);
	}
	dfsB(1,0);
	for(int i=1;i<=n;++i)write(ans[i],'\n');
	return 0;
}