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
| #include <iostream>
#include <algorithm>
#define maxn 300010
#define Maxn 600010
#define ll long long
using namespace std;
int n, m, k;
struct node {
int fr, to, w;
friend bool operator < (const node &u, const node &v) { return u.w < v.w; }
} E[maxn];
int fa[Maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
struct Edge {
int to, next;
} e[Maxn]; 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 a[Maxn], top, id[Maxn * 2], in[Maxn];
void dfs(int u, int fa) {
static int cnt = 0;
id[++cnt] = u; in[u] = cnt;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dfs(v, u); id[++cnt] = u;
}
}
inline int st_min(int l, int r) { return in[l] < in[r] ? l : r; }
int st[Maxn * 2][21], Log[Maxn * 2];
void init_st(int n) { Log[0] = -1;
for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
for (int i = 1; i <= n; ++i) st[i][0] = id[i];
for (int j = 1; j <= 20; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[i][j] = st_min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
inline int get_lca(int l, int r) {
if (!l || !r) return l + r;
l = in[l]; r = in[r]; if (l > r) swap(l, r);
int k = Log[r - l + 1];
return st_min(st[l][k], st[r - (1 << k) + 1][k]);
}
#define lc i << 1
#define rc i << 1 | 1
struct Seg {
int v, tag, lca;
} T[Maxn * 4];
inline void maintain(int i) { T[i].v = get_lca(T[lc].v, T[rc].v); }
void build(int i, int l, int r) {
if (l == r) return T[i].lca = l, void();
int m = l + r >> 1;
build(lc, l, m); build(rc, m + 1, r);
T[i].lca = get_lca(T[lc].lca, T[rc].lca);
}
inline void Update(int i, int tag) {
T[i].v = tag > 0 ? T[i].lca : 0;
T[i].tag = tag;
}
inline void pushdown(int i) {
int &tag = T[i].tag; if (!tag) return ;
Update(lc, tag); Update(rc, tag);
tag = 0;
}
void update(int i, int l, int r, int L, int R, int v) {
if (l > R || r < L) return ;
if (L <= l && r <= R) return Update(i, v);
int m = l + r >> 1; pushdown(i);
update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
maintain(i);
}
inline void solve_1() {
int x, y; cin >> x >> y;
update(1, 1, top, x, y, 1);
}
inline void solve_2() {
int x, y; cin >> x >> y;
update(1, 1, top, x, y, -1);
}
inline void solve_3() {
int x; cin >> x;
cout << (!T[1].v || T[1].v == x ? -1 : a[get_lca(x, T[1].v)]) << "\n";
}
int main() { fill(head, head + Maxn, -1);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m; top = n;
for (int i = 1; i < n; ++i) cin >> E[i].fr >> E[i].to >> E[i].w;
sort(E + 1, E + n); init_fa(2 * n);
for (int i = 1; i < n; ++i) {
int u = E[i].fr, v = E[i].to, w = E[i].w, fu, fv;
if ((fu = find(u)) == (fv = find(v))) continue;
fa[fu] = fa[fv] = ++top;
a[top] = w; add_edge(top, fu); add_edge(top, fv);
} dfs(top, 0); init_st(2 * top - 1); build(1, 1, top);
for (int i = 1; i <= m; ++i) {
int opt; cin >> opt;
switch (opt) {
case 1: solve_1(); break;
case 2: solve_2(); break;
case 3: solve_3(); break;
}
}
return 0;
}
|