好像复杂度来说不是正解……不加谜之优化（下叙）能被loj上的加强数据卡
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n, m, hea[100005], cnt, uu[200005], fa[100005], siz[100005], son[100005], idx;
int dfn[100005], top[100005], opt, vv[200005], ww[200005], dep[100005], xx, ans;
struct Edge{
int too, nxt;
}edge[200005], lian[100005];
struct SGTNode{
vector<int> vec1, vec2;
void insert(int x){
vec1.push_back(x);
push_heap(vec1.begin(), vec1.end());
}
void shanchu(int x){
vec2.push_back(x);
push_heap(vec2.begin(), vec2.end());
}
int getTop(){
while(true){
if(!vec1.size()) return -1;
if(!vec2.size()) return vec1[0];
if(vec1[0]==vec2[0]){
pop_heap(vec1.begin(), vec1.end());
vec1.pop_back();
pop_heap(vec2.begin(), vec2.end());
vec2.pop_back();
}
else return vec1[0];
}
}
};
struct SGT{
SGTNode nd[400005];
void update(int o, int l, int r, int x, int y, int w){
if(l>=x && r<=y){
if(opt==0) nd[o].insert(w);
else nd[o].shanchu(w);
}
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) update(lson, l, mid, x, y, w);
if(mid<y) update(rson, mid+1, r, x, y, w);
}
}
void query(int o, int l, int r, int x){
ans = max(ans, nd[o].getTop());
if(l==r) ;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) query(lson, l, mid, x);
else query(rson, mid+1, r, x);
}
}
}sgt;
bool cmp(const Edge &u, const Edge &v){
return u.too<v.too;
}
void add_edge(int fro, int too){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
hea[fro] = cnt;
}
void dfs1(int x, int f){
fa[x] = f;
dep[x] = dep[f] + 1;
siz[x] = 1;
int maxSon=-1;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f){
dfs1(t, x);
siz[x] += siz[t];
if(siz[t]>=maxSon){//就是这里，要写geq……
maxSon = siz[t];
son[x] = t;
}
}
}
}
void dfs2(int x, int topf){
dfn[x] = ++idx;
top[x] = topf;
if(!son[x]) return ;
dfs2(son[x], topf);
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=fa[x] && t!=son[x])
dfs2(t, t);
}
}
void rangeUpdate(int u, int v, int w){
int faq=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u, v);
lian[++faq] = (Edge){dfn[top[u]], dfn[u]};
u = fa[top[u]];
}
if(dep[u]>dep[v]) swap(u, v);
lian[++faq] = (Edge){dfn[u], dfn[v]};
sort(lian+1, lian+1+faq, cmp);
int lst=0;
for(int i=1; i<=faq; i++){
if(lst+1<=lian[i].too-1)
sgt.update(1, 1, n, lst+1, lian[i].too-1, w);
lst = lian[i].nxt;
}
if(lst+1<=n)
sgt.update(1, 1, n, lst+1, n, w);
}
int main(){
cin>>n>>m;
for(int i=1; i<n; i++){
scanf("%d %d", &xx, &ans);
add_edge(xx, ans);
add_edge(ans, xx);
}
dfs1(1, 0);
dfs2(1, 1);
for(int i=1; i<=m; i++){
scanf("%d", &opt);
if(opt==0){
scanf("%d %d %d", &uu[i], &vv[i], &ww[i]);
rangeUpdate(uu[i], vv[i], ww[i]);
}
else if(opt==1){
scanf("%d", &xx);
rangeUpdate(uu[xx], vv[xx], ww[xx]);
}
else{
scanf("%d", &xx);
ans = -1;
sgt.query(1, 1, n, dfn[xx]);
printf("%d
", ans);
}
}
return 0;
}