题解：树链剖分一下
对线段树每个节点维护双堆，支持插入删除
对于每一条请求，给这个请求没经过的点加入这个值，共logn个区间
查询就是线段树上的单点查询
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=1000000000;
const int maxn=200009;
int n,m,T;
int tx[maxn],ty[maxn],tv[maxn];
int cntedge;
int head[maxn];
int to[maxn],nex[maxn];
void Addedge(int x,int y){
nex[++cntedge]=head[x];
to[cntedge]=y;
head[x]=cntedge;
}
int father[maxn],depth[maxn],siz[maxn];
int idp[maxn],ref[maxn],hson[maxn],tp[maxn];
void Dfs(int now,int fa){
father[now]=fa;
depth[now]=depth[fa]+1;
siz[now]=1;
for(int i=head[now];i;i=nex[i]){
if(to[i]==fa)continue;
Dfs(to[i],now);
siz[now]+=siz[to[i]];
if(siz[to[i]]>=siz[hson[now]])hson[now]=to[i];
}
}
int dfsclock;
void Dfs2(int now,int toppoint){
idp[now]=++dfsclock;
ref[dfsclock]=now;
tp[now]=toppoint;
if(!hson[now])return;
Dfs2(hson[now],toppoint);
for(int i=head[now];i;i=nex[i]){
if(to[i]==father[now])continue;
if(to[i]==hson[now])continue;
Dfs2(to[i],to[i]);
}
}
priority_queue<int>q1[maxn<<1],q2[maxn<<1];
inline void Ins(int now,int val){
q1[now].push(val);
}
inline void Del(int now,int val){
q2[now].push(val);
while((!q1[now].empty())&&(!q2[now].empty())&&(q1[now].top()==q2[now].top())){
q1[now].pop();q2[now].pop();
}
}
inline int Mxp(int now){
if(!q1[now].empty())return q1[now].top();
else return -1;
}
void BuildTree(int now,int l,int r){
while(!q1[now].empty())q1[now].pop();
while(!q2[now].empty())q2[now].pop();
if(l==r)return;
int mid=(l+r)>>1;
BuildTree(now<<1,l,mid);
BuildTree(now<<1|1,mid+1,r);
}
void Updatasec(int now,int l,int r,int ll,int rr,int x,int opty){
// printf("%d %d %d %d %d
",now,l,r,ll,rr);
if(l>=ll&&r<=rr){
if(opty==1)Ins(now,x);
else Del(now,x);
return;
}
int mid=(l+r)>>1;
if(ll<=mid)Updatasec(now<<1,l,mid,ll,rr,x,opty);
if(rr>mid)Updatasec(now<<1|1,mid+1,r,ll,rr,x,opty);
}
int ans;
void Querymax(int now,int l,int r,int p){
ans=max(ans,Mxp(now));
if(l==r)return;
int mid=(l+r)>>1;
if(p<=mid)Querymax(now<<1,l,mid,p);
else Querymax(now<<1|1,mid+1,r,p);
}
struct Sec{
int l,r;
}s[maxn];
int nn;
int cmp(const Sec &rhs1,const Sec &rhs2){
return rhs1.l<rhs2.l;
}
void Insset(int u,int v,int val){
int tu=tp[u];
int tv=tp[v];
nn=0;
while(tu!=tv){
if(depth[tu]<depth[tv]){
swap(u,v);swap(tu,tv);
}
s[++nn].l=idp[tu];
s[nn].r=idp[u];
u=father[tu];tu=tp[u];
}
if(depth[u]>depth[v])swap(u,v);
s[++nn].l=idp[u];s[nn].r=idp[v];
sort(s+1,s+1+nn,cmp);
if(s[1].l!=1)Updatasec(1,1,n,1,s[1].l-1,val,1);
for(int i=1;i<nn;++i){
if(s[i].r<s[i+1].l-1)Updatasec(1,1,n,s[i].r+1,s[i+1].l-1,val,1);
}
if(s[nn].r!=n)Updatasec(1,1,n,s[nn].r+1,n,val,1);
}
void Delset(int u,int v,int val){
int tu=tp[u];
int tv=tp[v];
nn=0;
while(tu!=tv){
if(depth[tu]<depth[tv]){
swap(u,v);swap(tu,tv);
}
s[++nn].l=idp[tu];
s[nn].r=idp[u];
u=father[tu];tu=tp[u];
}
if(depth[u]>depth[v])swap(u,v);
s[++nn].l=idp[u];s[nn].r=idp[v];
sort(s+1,s+1+nn,cmp);
if(s[1].l!=1)Updatasec(1,1,n,1,s[1].l-1,val,0);
for(int i=1;i<nn;++i){
if(s[i].r<s[i+1].l-1)Updatasec(1,1,n,s[i].r+1,s[i+1].l-1,val,0);
}
if(s[nn].r!=n)Updatasec(1,1,n,s[nn].r+1,n,val,0);
}
int Getans(int x){
ans=-inf;
Querymax(1,1,n,idp[x]);
return ans;
}
int main(){
// freopen("sb.in","r",stdin);
// freopen("sb.out","w",stdout);
//
scanf("%d%d",&n,&T);
for(int i=1;i<=n-1;++i){
int x,y;scanf("%d%d",&x,&y);
Addedge(x,y);Addedge(y,x);
}
Dfs(1,0);
Dfs2(1,1);
BuildTree(1,1,n);
for(int i=1;i<=T;++i){
int opty,x,y,z;
scanf("%d%d",&opty,&x);
if(opty==0)scanf("%d%d",&y,&z);
if(opty==0){
Insset(x,y,z);
}
if(opty==1){
Delset(tx[x],ty[x],tv[x]);
}
if(opty==2){
// Getans(x);
printf("%d
",Getans(x));
}
if(opty==0){
tx[i]=x;ty[i]=y;tv[i]=z;
}
}
return 0;
}