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
| #include <iostream> #include <cstdio> #include <vector> #include <cstring> #define maxn 100010 #define pb push_back using namespace std;
int n, m, a[maxn], Max;
struct Edge { int to, next; } e[maxn * 2]; int c1, head[maxn]; inline void add_edge(int u, int v) { e[c1].to = v; e[c1].next = head[u]; head[u] = c1++; }
int f[maxn][21], dep[maxn]; void Dfs(int u, int fa) { for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if (v == fa) continue; dep[v] = dep[u] + 1; f[v][0] = u; Dfs(v, u); } }
void init_lca() { for (int j = 1; j <= 20; ++j) for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1]; }
int get_lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); for (int i = 20; ~i; --i) if (dep[f[x][i]] >= dep[y]) x = f[x][i]; if (x == y) return x; for (int i = 20; ~i; --i) if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; }
#define lc T[i].ch[0] #define rc T[i].ch[1] #define Lc T[j].ch[0] #define Rc T[j].ch[1] struct Seg { int v, s, ch[2]; } T[maxn * 20]; int top, rt[maxn]; inline void maintain(int i) { if (T[lc].s > T[rc].s || T[lc].s == T[rc].s && T[lc].v < T[rc].v) T[i].s = T[lc].s, T[i].v = T[lc].v; else T[i].s = T[rc].s, T[i].v = T[rc].v; }
void update(int &i, int l, int r, int k, int v) { if (!i) i = ++top; if (l == r) { T[i].s += v, T[i].v = l; if (!T[i].s) T[i].v = 0; return ; } int m = l + r >> 1; if (k <= m) update(lc, l, m, k, v); else update(rc, m + 1, r, k, v); maintain(i); }
void merge(int &i, int j, int l, int r) { if (!i) return (void) (i = j); if (!j) return ; if (l == r) { T[i].s += T[j].s, T[i].v = l; if (!T[i].s) T[i].v = 0; return ; } int m = l + r >> 1; merge(lc, Lc, l, m); merge(rc, Rc, m + 1, r); maintain(i); }
struct node { int x, y;
node() {} node(int _x, int _y) { x = _x; y = _y; } } ; vector<node> A[maxn]; int ans[maxn]; void dfs(int u, int fa) { for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if (v == fa) continue; dfs(v, u); merge(rt[u], rt[v], 1, Max); } for (auto it : A[u]) update(rt[u], 1, Max, it.x, it.y); ans[u] = T[rt[u]].v; }
int main() { memset(head, -1, sizeof head); cin >> n >> m; for (int i = 1; i < n; ++i) { int x, y; scanf("%d%d", &x, &y); add_edge(x, y); add_edge(y, x); } dep[1] = 1; Dfs(1, 0); init_lca(); for (int i = 1; i <= m; ++i) { int x, y, z, g; scanf("%d%d%d", &x, &y, &z); Max = max(Max, z); g = get_lca(x, y); A[g].pb(node(z, -1)); A[f[g][0]].pb(node(z, -1)); A[x].pb(node(z, 1)); A[y].pb(node(z, 1)); } dfs(1, 0); for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]); return 0; }
|