【DS】CF696E ...Wait for it...

考虑每个数只会删一次，意味着我们暴力找跟暴力删复杂度正确。

即问题变为

每个点是一个集合

1. 对于路径 \((u,v)\) 找每个集合的元素的最小值

2. 删去这个最小值

3. 子树加

考虑树剖，集合的话可以用 vector+启发式合并 之类的去维护线段树中一个点的区间集合并集，但是我们只需要维护最小值，于是对于线段树上的点记录最小值即可。

考虑删除，找到后暴力删。

对于线段树的标记，我们只需要正常下放，在删除的时候计算出最小值加了多少，把这些所加的保留即可。

注意时空常数。

#include 
#define ll long long
#define KG putchar(' ')
using namespace std;
// 树剖+线段树 维护小根堆
#define N (int)(2e5+5)
#define inf (ll)(2e18)
#define min(A,B) (Aq[N];
struct DAT {
	ll x; int id,pos;
	DAT(ll xx=inf,int idd=(int)(1e9),int poss=0) {
		x=xx; id=idd; pos=poss;
	}
	bool operator < (const DAT &rhs) const {
		return x==rhs.x?id>1;
		build(ls,l,mid); build(rs,mid+1,r);
		push_up(cur); 
	}
	void update(int cur,int l,int r,int cl,int cr,ll x) {
		if(cl<=l&&r<=cr) {
			T[cur].tag+=x; T[cur].mi.x+=x; return ;
		}
		push_down(cur);
		int mid=(l+r)>>1;
		if(cl<=mid) update(ls,l,mid,cl,cr,x);
		if(cr>mid) update(rs,mid+1,r,cl,cr,x);
		push_up(cur);
	}
	DAT query(int cur,int l,int r,int cl,int cr) {
		if(cl<=l&&r<=cr) {
		//	cout<<-T[cur].mi.x+T[cur].tag<<" "<<-T[cur].mi.id<>1;
		if(cr<=mid) return query(ls,l,mid,cl,cr);
		if(cl>mid) return query(rs,mid+1,r,cl,cr);
		return min(query(ls,l,mid,cl,cr),query(rs,mid+1,r,cl,cr));
		push_up(cur);
	}
	void del(int cur,int l,int r,int pos) {
		if(l==r) {
			ll qwq=q[rk[l]].front(); q[rk[l]].pop();
			if(q[rk[l]].empty()) T[cur].mi=DAT(inf,(int)(1e9),0);
			else {
				qwq=T[cur].mi.x-qwq+q[rk[l]].front();
				T[cur].mi=DAT(qwq,q[rk[l]].front(),l);
			}
			return ;
		}
		push_down(cur);
		int mid=(l+r)>>1;
		if(pos<=mid) del(ls,l,mid,pos);
		else del(rs,mid+1,r,pos);
		push_up(cur);
	}
} 

void add_edge(int x,int y) {
	e[++cnt].nex=hea[x]; e[cnt].to=y; hea[x]=cnt;
}

void dfs1(int x,int ff) {
	fa[x]=ff; dep[x]=dep[ff]+1; sz[x]=1;
	for(int i=hea[x];i;i=e[i].nex) {
		int y=e[i].to; if(y==ff) continue;
		dfs1(y,x); sz[x]+=sz[y];
		if(sz[y]>sz[son[x]]) son[x]=y;
	}
}

void dfs2(int x,int tpp) {
	tp[x]=tpp; id[x]=++tot; rk[tot]=x;
	if(son[x]) dfs2(son[x],tpp);
	for(int i=hea[x];i;i=e[i].nex) {
		int y=e[i].to; 
		if(y==son[x]||y==fa[x]) continue;
		dfs2(y,y);
	}
}

vectorans;
void solve(int fx,int fy,int z) {
	ans.clear();
	while(z--) {
		int x=fx,y=fy; DAT res=DAT(inf,(int)(1e9),0);
		while(tp[x]!=tp[y]) {
			if(dep[tp[x]]id[y]) swap(x,y);
		res=min(res,xgf::query(1,1,n,id[x],id[y]));
	//	cout<=inf) break;
		ans.push_back(res.id);
		xgf::del(1,1,n,res.pos);
	}
	cout<>n>>m>>Q;
	for(int i=1;i>x>>y;
		add_edge(x,y); add_edge(y,x);
	}
	for(int i=1;i<=m;i++) {
		cin>>x;
		q[x].push(i);
	}
	dfs1(1,0); dfs2(1,0); xgf::build(1,1,n);
	while(Q--) {
		cin>>op>>x>>y;
		if(op==1) {
			cin>>z;
			solve(x,y,z);
		} else {
			xgf::update(1,1,n,id[x],id[x]+sz[x]-1,1ll*y);
		}
	}
	return 0;		
}