如题，我在调这道题的时候，第一次用了如下代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,x,y,tot,first[N],Next[N*2],to[N*2],a[N],b[N],c[N];
int dep[N],f[N],siz[N],mson[N],zx[N],maxm;
int rt[N],cnt,id[N*30],val[N*30],ls[N*30],rs[N*30];
int Read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return f*x;
}
void add(int a,int b)
{
	tot++;
	Next[tot]=first[a];
	first[a]=tot;
	to[tot]=b;
}
void dfs1(int u,int fa)
{
	int Max=0;
	for(int i=first[u];i;i=Next[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dep[v]=dep[u]+1;
		f[v]=u;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>Max) Max=siz[v],mson[u]=v;
	}
}
void dfs2(int u,int zz)
{
	zx[u]=zz;
	if(mson[u]) dfs2(mson[u],zz);
	for(int i=first[u];i;i=Next[i])
	{
		int v=to[i];
		if(v==f[u]||v==mson[u]) continue;
		dfs2(v,v);
	}
}
int lca(int x,int y)
{
	while(zx[x]!=zx[y])
	{
		if(dep[zx[x]]<dep[zx[y]]) swap(x,y);
		x=f[zx[x]];
	}
	return dep[x]<dep[y]?x:y;
}
void pushup(int u)
{
	if(val[ls[u]]>=val[rs[u]]) val[u]=val[ls[u]],id[u]=id[ls[u]];
	else val[u]=val[rs[u]],id[u]=id[rs[u]];
	if(val[u]==0) id[u]=0;
}
void update(int &u,int l,int r,int st,int v)
{
	if(!u) u=++cnt;
	if(l==r)
	{
		val[u]+=v;
		id[u]=l;
		return;
	}
	int mid=(l+r)>>1;
	if(st<=mid) update(ls[u],l,mid,st,v);
	else update(rs[u],mid+1,r,st,v);
	pushup(u);
}
void merge(int &u,int v,int l,int r)
{
	
	if(!v) return;
	if(!u) u=++cnt;
	if(l==r)
	{
		val[u]+=val[v];
		id[u]=l;
		return;
	}
	int mid=(l+r)>>1;
	merge(ls[u],ls[v],l,mid);
	merge(rs[u],rs[v],mid+1,r);
	pushup(u);
	//cout<<u<<" "<<v<<" "<<l<<" "<<r<<" "<<val[u]<<" "<<id[u]<<endl;
}
void Find(int u)
{
	for(int i=first[u];i;i=Next[i])
	{
		int v=to[i];
		if(v==f[u]) continue;		
		Find(v);
		merge(rt[u],rt[v],1,maxm);
	}
}
int main()
{
	n=Read(),m=Read();
	for(int i=1;i<n;i++)
	{
		siz[i]=1;		
		x=Read(),y=Read();
		add(x,y),add(y,x);
	}
	siz[n]=1;
	dfs1(1,0),dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		a[i]=Read(),b[i]=Read(),c[i]=Read();
        maxm=max(maxm,c[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int zz=lca(a[i],b[i]);
		update(rt[a[i]],1,maxm,c[i],1);
		update(rt[b[i]],1,maxm,c[i],1);
		update(rt[zz],1,maxm,c[i],-1);
		if(f[zz]) update(rt[f[zz]],1,maxm,c[i],-1);
	}
	Find(1);
	for(int i=1;i<=n;i++) printf("%d\n",id[rt[i]]);
	return 0;
}

得了60分，后面的点全部TLE。

第二次，我修改了merge函数，如下：

int merge(int x,int y,int l,int r)
{
	if(!x||!y) return x+y;
	if(l==r) {val[x]+=val[y],id[x]=l;return x;}
	int mid=(l+r)>>1;
	ls[x]=merge(ls[x],ls[y],l,mid);
	rs[x]=merge(rs[x],rs[y],mid+1,r);
	pushup(x);
	return x;
}

没有TLE了，但是有很多WA，这次只有35分。

第三次，我修改了pushup函数和find，如下：

void pushup(int u)
{
	if(val[ls[u]]>=val[rs[u]]) val[u]=val[ls[u]],id[u]=id[ls[u]];
	else val[u]=val[rs[u]],id[u]=id[rs[u]];
}

void Find(int u)
{
	for(int i=first[u];i;i=Next[i])
	{
		int v=to[i];
		if(v==f[u]) continue;		
		Find(v);
		merge(rt[u],rt[v],1,maxm);
	}
	if(val[rt[u]]) ans[u]=id[rt[u]];
}

这一次莫名其妙AC了。

请问这到底是怎么回事？