1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| #include<bits/stdc++.h>
using namespace std;
#define LOG 19
#define N 6000005
vector<int> mp[100005];
struct segt
{
int ls,rs;
int mxn,mxnp;
}tr[N<<2];
int fa[100005][20],dep[100005];
int L,rt[100005],ans[100005],a[100005],b[100005],c[100005];
int n,m,tot=0;
void dfs(int u,int f)
{
fa[u][0]=f;
dep[u]=dep[f]+1;
for(int i=1;i<=LOG;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=0;i<mp[u].size();i++)
{
if(mp[u][i]!=f)
dfs(mp[u][i],u);
}
}
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=LOG;i>=0&&dep[u]!=dep[v];i--)
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];
if(u==v) return u;
for(int i=LOG;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
void pushup(int x)
{
if(tr[tr[x].ls].mxn>=tr[tr[x].rs].mxn)
{
tr[x].mxn=tr[tr[x].ls].mxn;
tr[x].mxnp=tr[tr[x].ls].mxnp;
}
else
{
tr[x].mxn=tr[tr[x].rs].mxn;
tr[x].mxnp=tr[tr[x].rs].mxnp;
}
}
int change(int x,int l,int r,int p,int c)
{
if(!x) x=++tot;
if(l==r)
{
tr[x].mxn+=c,tr[x].mxnp=l;
return x;
}
int mid=(l+r)>>1;
if(mid>=p) tr[x].ls=change(tr[x].ls,l,mid,p,c);
else tr[x].rs=change(tr[x].rs,mid+1,r,p,c);
pushup(x);
return x;
}
int merge(int x,int y,int l,int r)
{
if(!x||!y) return x+y;
if(l==r)
{
tr[x].mxn+=tr[y].mxn;
tr[x].mxnp=l;
return x;
}
int mid=(l+r)>>1;
tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid);
tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
pushup(x);
return x;
}
void getans(int x)
{
for(int i=0;i<mp[x].size();i++)
if(mp[x][i]!=fa[x][0])
{
getans(mp[x][i]);
rt[x]=merge(rt[x],rt[mp[x][i]],1,L);
}
if(tr[rt[x]].mxn)
ans[x]=tr[rt[x]].mxnp;
}
int main()
{
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
mp[u].push_back(v);
mp[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=m;i++)
{
cin>>a[i]>>b[i]>>c[i];
L=max(L,c[i]);
}
for(int i=1;i<=m;i++)
{
int anc=lca(a[i],b[i]);
rt[a[i]]=change(rt[a[i]],1,L,c[i],1);
rt[b[i]]=change(rt[b[i]],1,L,c[i],1);
rt[anc]=change(rt[anc],1,L,c[i],-1);
if(fa[anc][0]) rt[fa[anc][0]]=change(rt[fa[anc][0]],1,L,c[i],-1);
}
getans(1);
for(int i=1;i<=n;i++)
cout<<ans[i]<<endl;
return 0;
}
|
