传送门
已经极其接近的想到过正确做法了，但是没想到标记永久化，所以复杂度炸了
树链剖分，对于线段树每个节点开个堆（一开始用multiset，结果MLE了，想不通为什么）
考虑对于一次请求(u，v)，只有当它的路径上的点坏掉的时候，它才会受到影响，所以除去这条路径上的所有点都应该有这个贡献
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e5+10;
int n,m,cnt,pre[maxn*2],nxt[maxn*2],h[maxn],size[maxn],dep[maxn];
int f[maxn],top[maxn],id[maxn],tmp,tot,x[maxn*2],y[maxn*2],z[maxn*2],ans;
struct o{int x,y;}w[maxn];
priority_queue<int>q[maxn*4],p[maxn*4];
int get_top(int x)
{
while(!q[x].empty()&&!p[x].empty()&&q[x].top()==p[x].top())q[x].pop(),p[x].pop();
return q[x].empty()?0:q[x].top();
}
struct oo{int l,r;}s[maxn*4];
void add(int x,int y)
{
pre[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt;
pre[++cnt]=x,nxt[cnt]=h[y],h[y]=cnt;
}
void dfs(int x,int fa)
{
size[x]=1;
for(rg int i=h[x];i;i=nxt[i])
if(pre[i]!=fa)
{
f[pre[i]]=x,dep[pre[i]]=dep[x]+1,
dfs(pre[i],x),size[x]+=size[pre[i]];
}
}
void dfs1(int x,int f)
{
top[x]=f,id[x]=++tmp;int k=0;
for(int i=h[x];i;i=nxt[i])
if(dep[pre[i]]>dep[x]&&size[pre[i]]>=size[k])k=pre[i];
if(!k)return ;dfs1(k,f);
for(rg int i=h[x];i;i=nxt[i])
if(dep[pre[i]]>dep[x]&&pre[i]!=k)dfs1(pre[i],pre[i]);
}
void build(int x,int l,int r)
{
s[x].l=l,s[x].r=r;int mid=(l+r)>>1;
if(l==r)return ;
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
bool cmp(o a,o b){return a.x<b.x;}
void change(int x,int l,int r,int v,int id)
{
if(l<=s[x].l&&r>=s[x].r)
{
if(id)q[x].push(v);else p[x].push(v);
return ;
}
int mid=(s[x].l+s[x].r)>>1;
if(l<=mid)change(x<<1,l,r,v,id);
if(r>mid)change(x<<1|1,l,r,v,id);
}
void modify(int x,int y,int val,int flag)
{
tot=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
w[++tot]=(o){id[top[x]],id[x]};
x=f[top[x]];
}
if(id[x]>id[y])swap(x,y);
w[++tot]=(o){id[x],id[y]};
sort(w+1,w+tot+1,cmp);int las=1;
for(rg int i=1;i<=tot;i++)
{
if(las<=w[i].x-1)change(1,las,w[i].x-1,val,flag);
las=w[i].y+1;
}
if(las<=n)change(1,las,n,val,flag);
}
int get(int x,int t)
{
if(s[x].l==s[x].r)return get_top(x);
int mid=(s[x].l+s[x].r)>>1,ans=get_top(x);
if(t<=mid)return max(get(x<<1,t),ans);
else return max(get(x<<1|1,t),ans);
}
int main()
{
read(n),read(m);
for(rg int i=1,u,v;i<n;i++)read(u),read(v),add(u,v);
dfs(1,0),dfs1(1,1),build(1,1,n);
for(rg int i=1,opt,t;i<=m;i++)
{
read(opt);
if(opt==0)
{
read(x[i]),read(y[i]),read(z[i]);
modify(x[i],y[i],z[i],1);
}
if(opt==1)
{
read(t);
modify(x[t],y[t],z[t],0);
}
if(opt==2)read(t),ans=get(1,id[t]),printf("%d
",ans?ans:-1);
}
}