自动搬运

查看原文

来自洛谷，原作者为

	Salamander **

搬运于2025-08-24 21:46:58，当前版本为作者最后更新于2018-03-28 19:17:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

用时间线段树或者直接暴力维护是$O(n\log^3n)$的，虽然卡卡常可以过但是有更好的做法。

考虑二分答案，如果某个询问点被所有大于当前答案的路径所经过，那么答案小于等于当前答案，否则大于等于当前答案。查询经过一个点的路径条数，把路径两端点权加一，然后lca和lca父亲的点权减一，用树状数组维护一下子树权值和即可。

但是我们还要考虑一条路径在当前时刻是否出现，以及计算出比当前答案大的路径有多少条。

所以我们考虑整体二分。整体二分中当前部分的各个操作依旧是按照时间顺序进行的，可以同时维护当前时刻路径是否存在，以及计算出比当前答案大的路径有多少条。

假设当前二分的答案是mid，要处理的操作队列为q。我们只需要扫一遍q，如果是询问那么就查询一下经过它的路径，判断它下次会被丢到左边递归还是丢到右边递归；如果是修改，那么如果这次修改对应的路径权值大于mid，就进行修改，然后丢到右边递归，否则对当前情况下其他的询问没有影响，直接丢到左边递归即可。

复杂度$O(n\log^2n)$，不需要任何优化跑得飞快。

#include<bits/stdc++.h>
using std::vector;

#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)

template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
	T f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	x*=f;
}

const int maxn=200010;
struct edge{
	int to,nxt;
}e[maxn];
struct Query{
	int op,t,x,res;
	bool operator<(const Query &b)const{return t<b.t;}
}q[maxn],ql[maxn],qr[maxn];
int n,m,num,head[maxn],c[maxn];
int fa[maxn],top[maxn],size[maxn],son[maxn],dep[maxn];
int A[maxn],B[maxn],C[maxn],tL[maxn],tR[maxn],dfn,mx;

void add(int,int);
int qry(int);
int qry(int,int);
void addedge(int,int);
void Dfs1(int,int);
void Dfs2(int,int);
int lca(int,int);
void Solve(int,int,int,int);
void modify(int,int,int);

int main(){
	read(n);read(m);
	For(i,1,n-1){
		int u,v;read(u);read(v);
		addedge(u,v);
	}
	Dfs1(1,0);Dfs2(1,1);
	For(i,1,m){
		read(q[i].op);
		q[i].t=i;
		if(!q[i].op){
			read(A[i]);read(B[i]);
			read(C[i]);
			q[i].x=i;
			chkmax(mx,C[i]);
		}
		else read(q[i].x);
	}
	Solve(-1,mx,1,m);
	std::sort(q+1,q+m+1);
	For(i,1,m) if(q[i].op==2) printf("%d\n",q[i].res);
	return 0;
}

void Solve(int l,int r,int L,int R){
	if(l==r){
		For(i,L,R) if(q[i].op==2) q[i].res=l;
		return;
	}
	int mid=(l+r)>>1,path=0,cntl=0,cntr=0;
	For(i,L,R){
		if(q[i].op==2){
			if(qry(tL[q[i].x],tR[q[i].x])==path) ql[++cntl]=q[i];
			else qr[++cntr]=q[i];
		}
		else{
			if(C[q[i].x]<=mid) ql[++cntl]=q[i];
			else{
				int v=q[i].op?-1:1;
				path+=v;
				modify(A[q[i].x],B[q[i].x],v);
				qr[++cntr]=q[i];
			}
		}
	}
	For(i,1,cntr) if(qr[i].op!=2){
		int v=qr[i].op?1:-1;
		modify(A[qr[i].x],B[qr[i].x],v);
	}
	For(i,1,cntl) q[L+i-1]=ql[i];
	For(i,1,cntr) q[L+cntl+i-1]=qr[i];
	if(cntl) Solve(l,mid,L,L+cntl-1);
	if(cntr) Solve(mid+1,r,L+cntl,R);
}
void modify(int x,int y,int v){
	int z=lca(x,y);
	add(tL[x],v);add(tL[y],v);add(tL[z],-v);
	if(fa[z]) add(tL[fa[z]],-v);
}
void Dfs1(int x,int f){
	dep[x]=dep[fa[x]=f]+1;
	size[x]=1;tL[x]=++dfn;
	for(int i=head[x];i;i=e[i].nxt)
		if(e[i].to!=f){
			Dfs1(e[i].to,x);
			size[x]+=size[e[i].to];
			if(size[e[i].to]>size[son[x]]) son[x]=e[i].to;
		}
	tR[x]=dfn;
}
void Dfs2(int x,int tp){
	top[x]=tp;
	if(son[x]) Dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].nxt)
		if(e[i].to!=fa[x]&&e[i].to!=son[x])
			Dfs2(e[i].to,e[i].to);
}
int lca(int u,int v){
	int x=top[u],y=top[v];
	while(x!=y){
		if(dep[x]>dep[y]) x=top[u=fa[x]];
		else y=top[v=fa[y]];
	}
	return dep[u]<dep[v]?u:v;
}
void addedge(int u,int v){
	e[++num].to=v;e[num].nxt=head[u];head[u]=num;
	e[++num].to=u;e[num].nxt=head[v];head[v]=num;
}
void add(int x,int v){for(;x<=n;x+=x&-x) c[x]+=v;}
int qry(int x){
	int res=0;
	for(;x;x-=x&-x) res+=c[x];
	return res;
}
int qry(int l,int r){return qry(r)-qry(l-1);}