RT,为什么T了,求助大佬们
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int ct;
int fa[N][22];
int x[2*N],v[2*N];
int al[N],dep[N],ans[N];
struct data{
int u,cnt;
friend bool operator < (data a,data b){
return (a.cnt==b.cnt) ? a.u>b.u : a.cnt<b.cnt;
}
friend data operator + (data a,data b){
return (data){a.u,a.cnt+b.cnt};
}
};
vector<data> ve[N];
inline void add(int u,int sum)
{
v[++ct]=sum;
x[ct]=al[u];
al[u]=ct;
}
struct onlinetree{
int ct;
int s[40*N][2];
data v[40*N];
inline void ih()
{
ct=n;
}
inline void ins(int p,int l,int r,data va)
{
if(r-l==1){
v[p]=va+v[p];
return ;
}
int mid=(l+r)/2;
if(va.u<=mid)
ins(s[p][0]==s[p][0] ? s[p][0] : ++ct,l,mid,va);
else
ins(s[p][1]==s[p][1] ? s[p][1] : ++ct,mid,r,va);
v[p]=max(v[s[p][0]],v[s[p][1]]);
}
inline void mg(int p1,int p2,int l,int r)
{
if(r-l==1){
v[p1]=v[p1]+v[p2];
return ;
}
int mid=(l+r)/2;
if(s[p1][0]&&s[p2][0])
mg(s[p1][0],s[p2][0],l,mid);
else if(s[p2][0])
s[p1][0]=s[p2][0];
if(s[p1][1]&&s[p2][1])
mg(s[p1][1],s[p2][1],mid,r);
else if(s[p2][1]);
s[p2][1]=s[p2][1];
v[p1]=max(v[s[p1][0]],v[s[p1][1]]);
}
}lt;
inline int dfs1(int u)
{
int i;
for(i=0;fa[u][i];i++)
fa[u][i+1]=fa[fa[u][i]][i];
dep[u]=dep[fa[u][0]]+1;
for(i=al[u];i;i=x[i])
if(v[i]!=fa[u][0]){
fa[v[i]][0]=u;
dfs1(v[i]);
}
}
inline int lca(int u,int v)
{
if(dep[u]<dep[v])
swap(u,v);
int i,j;
for(j=dep[u]-dep[v],i=0;j;j>>=1,i++)
if(j&1)
u=fa[u][i];
if(u==v)
return u;
for(i=18;i>=0;i--)
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];
v=fa[v][i];
}
return fa[u][0];
}
inline void dfs2(int u)
{
int i;
for(i=al[u];i;i=x[i])
if(v[i]!=fa[u][0]){
dfs2(v[i]);
lt.mg(u,v[i],0,1e5);
}
vector<data>::iterator it;
for(it=ve[u].begin();it!=ve[u].end();it++)
lt.ins(u,0,1e5,*it);
ans[u]=lt.v[u].u;
}
int main()
{
cin>>n>>m;
lt.ih();
int i;
for(i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
dfs1(1);
for(i=1;i<=m;i++){
int u,v,va;
cin>>u>>v>>va;
int lc=lca(u,v);
ve[u].push_back((data){va,1});
ve[v].push_back((data){va,1});
ve[lc].push_back((data){va,-1});
ve[fa[lc][0]].push_back((data){va,-1});
}
dfs2(1);
for(i=1;i<=n;i++)
cout<<ans[i]<<endl;
return 0;
}