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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| #include<bits/stdc++.h>
using namespace std;
const int MAXn = 1e5;
const int MAXm = 1e5;
const int MAXz = 1e5;
const int MAXlayz = 18;
const int NINF = 0xc0c0c0c0;
template <typename T>
inline void read(T &a) {
char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
read(a), read(argv...);
}
int head[MAXn + 10], cntnex, nex[MAXn * 2 + 10], to[MAXn * 2 + 10];
inline void connect(int u, int v) {
nex[++cntnex] = head[u];
head[u] = cntnex;
to[cntnex] = v;
}
int fa[MAXn + 10], dep[MAXn + 10], siz[MAXn + 10], hson[MAXn + 10];
void dfs1(int cur, int f) {
fa[cur] = f;
dep[cur] = dep[f] + 1;
siz[cur] = 1;
int mxsonsiz = 0;
for (int i = head[cur]; i; i = nex[i]) {
if (to[i] == fa[cur]) continue;
dfs1(to[i], cur);
siz[cur] += siz[to[i]];
if (mxsonsiz < siz[to[i]]) {
mxsonsiz = siz[to[i]];
hson[cur] = to[i];
}
}
}
int cntdfs, nddfs[MAXn + 10], idxdfs[MAXn + 10], top[MAXn + 10];
void dfs2(int cur, int tp) {
top[cur] = tp;
nddfs[cur] = ++cntdfs;
idxdfs[cntdfs] = cur;
if (hson[cur]) {
dfs2(hson[cur], top[cur]);
}
for (int i = head[cur]; i; i = nex[i]) {
if (to[i] == fa[cur] || to[i] == hson[cur]) continue;
dfs2(to[i], to[i]);
}
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) swap(x, y);
y = fa[top[y]];
}
if (dep[x] > dep[y]) swap(x, y);
return x;
}
struct Ele {
int z, opt;
};
vector<Ele> ndele[MAXn + 10];
struct Info {
int cnt, idx;
inline bool operator>(const Info sec) const {
if (cnt != sec.cnt) return cnt > sec.cnt;
else return idx < sec.idx;
}
inline Info operator+(const Info sec) const {
return Info{cnt + sec.cnt, idx};
}
};
inline Info max(Info fir, Info sec) {
return (fir > sec) ? fir : sec;
}
const int MAXnd = MAXm * 4 * MAXlayz;
int root[MAXn + 10];
int cntnd, ls[MAXnd + 10], rs[MAXnd + 10];
Info info[MAXnd + 10];
inline void pushup(int id) {
info[id] = max(info[ls[id]], info[rs[id]]);
}
void modify(int &id, int p, int v, int le, int ri) {
if (id == 0) id = ++cntnd;
if (le == ri) {
info[id].idx = le;
info[id].cnt += v;
if (info[id].cnt == 0) info[id] = Info{0, 0};
} else {
int mid = (le + ri) >> 1;
if (p <= mid) modify(ls[id], p, v, le, mid);
else modify(rs[id], p, v, mid + 1, ri);
pushup(id);
}
}
int merge(int id1, int id2, int le, int ri) {
if (id1 == 0 || id2 == 0) return id1 + id2;
if (le == ri) {
info[id1] = info[id1] + info[id2];
if (info[id1].cnt == 0) info[id1] = Info{0, 0};
} else {
int mid = (le + ri) >> 1;
ls[id1] = merge(ls[id1], ls[id2], le, mid);
rs[id1] = merge(rs[id1], rs[id2], mid + 1, ri);
pushup(id1);
}
return id1;
}
int mxz;
int ans[MAXn + 10];
void dfs3(int cur) {
for (int i = head[cur]; i; i = nex[i]) {
if (to[i] == fa[cur]) continue;
dfs3(to[i]);
root[cur] = merge(root[cur], root[to[i]], 1, mxz);
}
for (auto i: ndele[cur]) {
modify(root[cur], i.z, i.opt, 1, mxz);
}
ans[cur] = info[root[cur]].idx;
}
int n, m;
signed main() {
read(n, m);
for (int i = 1, u, v; i < n; ++i) {
read(u, v);
connect(u, v); connect(v, u);
}
dfs1(1, 0);
dfs2(1, 1);
for (int i = 1, x, y, z; i <= m; ++i) {
read(x, y, z);
mxz = max(mxz, z);
int lcaa = lca(x, y);
ndele[x].push_back(Ele{z, 1});
ndele[y].push_back(Ele{z, 1});
ndele[lcaa].push_back(Ele{z, -1});
if (fa[lcaa]) ndele[fa[lcaa]].push_back(Ele{z, -1});
}
dfs3(1);
for (int i = 1; i <= n; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}
|
