|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 100010, M = N << 1;
|
|
|
|
|
|
struct Node {
|
|
|
int l, r;
|
|
|
int maxv, pos; // maxv 表示物品最大值，pos 表示物品最大值对应的类型离散化后的编号
|
|
|
} tr[N * 4 * 17];
|
|
|
|
|
|
int root[N], cnt; //记录每个节点对应的线段树的根节点的下标
|
|
|
|
|
|
struct Query {
|
|
|
int x, y, z;
|
|
|
} query[N]; //记录所有查询
|
|
|
|
|
|
int n, m;
|
|
|
int h[N], e[M], ne[M], idx; //邻接表
|
|
|
int dep[N], fa[N][17]; // dep[i] 表示节点 i 的深度，fa[i][j] 表示节点 i 向上走 2^j 步到达的节点
|
|
|
int q[N]; //队列
|
|
|
vector<int> nums; //离散化
|
|
|
int res[N]; //记录每个节点的答案
|
|
|
|
|
|
//离散化
|
|
|
int find(int x) {
|
|
|
int l = 0, r = nums.size() - 1;
|
|
|
while (l < r) {
|
|
|
int mid = (l + r) >> 1;
|
|
|
if (nums[mid] >= x)
|
|
|
r = mid;
|
|
|
else
|
|
|
l = mid + 1;
|
|
|
}
|
|
|
return r + 1; //所有类型的编号从1开始，加上一个偏移量
|
|
|
}
|
|
|
|
|
|
void add(int a, int b) { //添加边
|
|
|
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
void bfs() { //预处理 dep[], fa[][]
|
|
|
queue<int> q;
|
|
|
q.push(1);
|
|
|
dep[1] = 1;
|
|
|
while (q.size()) {
|
|
|
int t = q.front();
|
|
|
q.pop();
|
|
|
for (int i = h[t]; ~i; i = ne[i]) {
|
|
|
int j = e[i];
|
|
|
if (dep[j]) continue;
|
|
|
dep[j] = dep[t] + 1;
|
|
|
fa[j][0] = t;
|
|
|
for (int k = 1; k <= 16; k++)
|
|
|
fa[j][k] = fa[fa[j][k - 1]][k - 1];
|
|
|
q.push(j);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int lca(int a, int b) { //求 a 和 b 的最近公共祖先
|
|
|
if (dep[a] < dep[b]) swap(a, b);
|
|
|
for (int k = 16; k >= 0; k--)
|
|
|
if (dep[fa[a][k]] >= dep[b])
|
|
|
a = fa[a][k];
|
|
|
if (a == b) return a;
|
|
|
for (int k = 16; k >= 0; k--)
|
|
|
if (fa[a][k] != fa[b][k]) {
|
|
|
a = fa[a][k];
|
|
|
b = fa[b][k];
|
|
|
}
|
|
|
return fa[a][0];
|
|
|
}
|
|
|
|
|
|
void pushup(int u) { //用子节点信息更新父节点信息
|
|
|
tr[u].maxv = max(tr[tr[u].l].maxv, tr[tr[u].r].maxv);
|
|
|
//如果多个物品数量相同，优先记录最靠左的物品编号
|
|
|
tr[u].pos = tr[tr[u].l].maxv >= tr[tr[u].r].maxv ? tr[tr[u].l].pos : tr[tr[u].r].pos;
|
|
|
}
|
|
|
|
|
|
void insert(int u, int l, int r, int x, int v) { //将 x 类型 + v
|
|
|
if (l == r) { //找到指定类型
|
|
|
tr[u].maxv += v; //修改物品个数
|
|
|
tr[u].pos = tr[u].maxv ? l : 0; //如果物品还有，保存下标，如果物品为空，为 0
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
int mid = (l + r) >> 1;
|
|
|
if (x <= mid) { //递归左区间
|
|
|
if (!tr[u].l) tr[u].l = ++cnt; //如果左子节点不存在，动态开点
|
|
|
insert(tr[u].l, l, mid, x, v);
|
|
|
} else { //递归右区间
|
|
|
if (!tr[u].r) tr[u].r = ++cnt; //如果右子节点不存在，动态开点
|
|
|
insert(tr[u].r, mid + 1, r, x, v);
|
|
|
}
|
|
|
pushup(u); //用子节点信息更新父节点信息
|
|
|
}
|
|
|
|
|
|
int merge(int u, int v, int l, int r) { //线段树合并
|
|
|
if (!u) return v; //如果 u 不存在，直接返回 v
|
|
|
if (!v) return u; //如果 v 不存在，直接返回 u
|
|
|
|
|
|
if (l == r) { //如果是单独一个节点
|
|
|
tr[u].maxv += tr[v].maxv; //节点合并
|
|
|
tr[u].pos = tr[u].maxv ? l : 0;
|
|
|
return u;
|
|
|
}
|
|
|
|
|
|
int mid = (l + r) >> 1;
|
|
|
tr[u].l = merge(tr[u].l, tr[v].l, l, mid); //合并左子节点
|
|
|
tr[u].r = merge(tr[u].r, tr[v].r, mid + 1, r); //合并右子节点
|
|
|
pushup(u); //用子节点信息更新父节点信息
|
|
|
return u;
|
|
|
}
|
|
|
|
|
|
void dfs(int u) { // dfs求以每个节点为根节点的子树和
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int j = e[i];
|
|
|
if (dep[j] <= dep[u]) continue; //只能往下走
|
|
|
dfs(j); //搜索子节点
|
|
|
root[u] = merge(root[u], root[j], 1, nums.size()); //合并
|
|
|
}
|
|
|
res[u] = tr[root[u]].pos; //记录当前节点的答案(子树和)
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//优化读入
|
|
|
ios::sync_with_stdio(false);
|
|
|
cin.tie(0);
|
|
|
cout.tie(0);
|
|
|
|
|
|
memset(h, -1, sizeof h); //初始化邻接表
|
|
|
cin >> n >> m;
|
|
|
for (int i = 1; i < n; i++) {
|
|
|
int a, b;
|
|
|
cin >> a >> b;
|
|
|
add(a, b), add(b, a); //无向边
|
|
|
}
|
|
|
bfs(); //预处理 dep[], fa[][]
|
|
|
|
|
|
for (int i = 1; i <= n; i++) root[i] = ++cnt; //为每个节点开一个动态开点的线段树
|
|
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
|
cin >> query[i].x >> query[i].y >> query[i].z;
|
|
|
nums.push_back(query[i].z);
|
|
|
}
|
|
|
//离散化
|
|
|
sort(nums.begin(), nums.end());
|
|
|
nums.erase(unique(nums.begin(), nums.end()), nums.end());
|
|
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
|
int x = query[i].x, y = query[i].y, z = find(query[i].z);
|
|
|
int p = lca(x, y);
|
|
|
insert(root[x], 1, nums.size(), z, 1); // c[x][z] + 1
|
|
|
insert(root[y], 1, nums.size(), z, 1); // c[y][z] + 1
|
|
|
insert(root[p], 1, nums.size(), z, -1); // c[lca(x, y)][z] - 1
|
|
|
if (fa[p][0]) insert(root[fa[p][0]], 1, nums.size(), z, -1); // c[fa(lca(x, y))][z] - 1
|
|
|
}
|
|
|
dfs(1); //求子树和
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
printf("%d\n", nums[res[i] - 1]); //将离散化的编号还原到原编号，要减去之前加上的一个偏移量
|
|
|
|
|
|
return 0;
|
|
|
} |
