rt ,TLE 65 分,求助!
#include"iostream"
#include"cstdio"
#include"cmath"
using namespace std;
#define MAXN 100005
#define read(x) scanf("%d",&x)
int n,m,u,v,c;
int dep[MAXN],top[MAXN],f[MAXN],son[MAXN],tot[MAXN];
struct node
{
int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt=0;
struct Tree
{
int ls,rs,maxn,pos;
}a[MAXN*25];
int opt=0,root[MAXN];
int ans[MAXN];
void add(int u,int v){e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;}
int dfs1(int cur,int fa)
{
f[cur]=fa,dep[cur]=dep[fa]+1,tot[cur]=1;
int maxn=0;
for(int i=head[cur];i;i=e[i].nxt)
{
int j=e[i].to;
if(j==fa) continue;
int op=dfs1(j,cur);
tot[cur]+=op;
if(maxn<op) maxn=op,son[cur]=j;
}
return tot[cur];
}
void dfs2(int cur,int topf)
{
top[cur]=topf;
if(son[cur]) dfs2(son[cur],topf);
for(int i=head[cur];i;i=e[i].nxt)
{
int j=e[i].to;
if(j==f[cur]||j==son[cur]) continue;
dfs2(j,j);
}
}
int LCA(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=f[top[u]];
}
return (dep[u]<dep[v])?u:v;
}
void update(int k)
{
if(a[a[k].ls].maxn>=a[a[k].rs].maxn)
a[k].maxn=a[a[k].ls].maxn,a[k].pos=a[a[k].ls].pos;
else
a[k].maxn=a[a[k].rs].maxn,a[k].pos=a[a[k].rs].pos;
}
int modify(int &k,int l,int r,int x,int y)
{
if(!k) k=++opt;
if(l==r)
{
a[k].maxn+=y,a[k].pos=l;
return k;
}
int mid=(l+r)>>1;
if(x<=mid) a[k].ls=modify(a[k].ls,l,mid,x,y);
else a[k].rs=modify(a[k].rs,mid+1,r,x,y);
update(k);
return k;
}
int merge(int u,int v,int l,int r)
{
if(!u||!v) return u|v;
if(l==r)
{
a[u].maxn+=a[v].maxn;
a[u].pos=l;
return u;
}
int mid=(l+r)>>1;
a[u].ls=merge(a[u].ls,a[v].ls,l,mid);
a[u].rs=merge(a[u].rs,a[v].rs,mid+1,r);
update(u);
return u;
}
void dfs(int cur)
{
for(int i=head[cur];i;i=e[i].nxt)
{
int j=e[i].to;
if(j==f[cur]) continue;
dfs(j);
root[cur]=merge(root[cur],root[j],1,100000);
}
if(a[root[cur]].maxn) ans[cur]=a[root[cur]].pos;
}
int main()
{
read(n),read(m);
for(int i=1;i<n;i++) read(u),read(v),add(u,v),add(v,u);
dfs1(1,1),dfs2(1,1);
for(int i=1;i<=m;i++)
{
read(u),read(v),read(c);
int now=LCA(u,v);
root[u]=modify(root[u],1,100000,c,1);
root[v]=modify(root[v],1,100000,c,1);
root[now]=modify(root[now],1,100000,c,-1);
if(f[now]^now) root[f[now]]=modify(root[f[now]],1,100000,c,-1);
}
dfs(1);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}