自动搬运

查看原文

来自洛谷，原作者为

	鲤鱼江 精神状况堪忧 | 我是？

搬运于2025-08-24 22:50:19，当前版本为作者最后更新于2024-07-22 17:22:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先放一个帖子：link。

这题有一个细节，后面再说。

首先我们发现这个题面十分抽象，所以先提取关键信息，发现没有 $3$ 操作的问题可以转化为：走边权不超过 $k$ 的边能走到多少点，其实也就是瓶颈路问题。

考虑 Kruskal 重构树，则每次能走到的点对应到重构树上刚好就是一个子树，因为 LCA 肯定是瓶颈，既然 LCA 都能走，子树内一定畅通无阻。

那这个方法对于有 $3$ 操作的该题是否有启发呢？答案是显然的。不然我为啥讲。

发现权值的相对关系始终不变，所以树的形态也一定不会变，所以每次修改边权就直接修改 LCA 的点权就行了，不过要提前判断这条边是否在 Kruskal 重构树上，否则只有 $90$ 分。

然后就牵扯到上面的帖子了，题面中说了修改边权不会是断掉的边是不会重连的，所以有些题解的代码有点问题。

具体实现 $3$ 操作的方式有很多，我在代码中选择使用 vector 进行懒删除，每次操作 $1$ 时集体下放修改。

还有就是这道题你不管操作 $3$ 也有 $90$ 分，数据很水。

#include<bits/stdc++.h>

using namespace std;

namespace Fread {
	const int SIZE=1<<21;char buf[SIZE],*S,*T;
	inline char getchar() {if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite {
	const int SIZE=1<<21;
	char buf[SIZE],*S=buf,*T=buf+SIZE;
	inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
	inline void putchar(char c){*S++=c;if(S==T)flush();}
	struct POPOSSIBLE{~POPOSSIBLE(){flush();}}ztr;
}
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
namespace Fastio{
	struct Reader{
	    template<typename T>
    	Reader& operator >> (T& x) {
        	char c=getchar();T f=1;
        	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}x=0;
        	while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}x*=f;
	        return *this;
    	}
	    Reader(){}
	}cin;
	struct Writer{
	    template<typename T>
	    Writer& operator << (T x) {
	        if(x==0){putchar('0');return *this;}
	        if(x<0){putchar('-');x=-x;}
	        static int sta[45];int top=0;
	        while(x){sta[++top]=x%10;x/=10;}
	        while(top){putchar(sta[top]+'0');--top;}
	        return *this;
    	}
    	Writer& operator << (char c) {putchar(c);return *this;}
    	Writer& operator << (const char* str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
    	Writer(){}
	}cout;
}
#define fi first
#define endl '\n'
#define sec second
#define mk make_pair
#define cin Fastio :: cin
#define cout Fastio :: cout

const int B=20;
const int N=1e6+10;
typedef pair<int,int> pii;
struct edge{
	int x,y,z;
	edge(int x=0,int y=0,int z=0):x(x),y(y),z(z){;}
	bool operator <(const edge &t)const{return z>t.z;}
}a[N],b[N];
int siz[N],f[N][B+1],fa[N],ls[N],rs[N],tot,n,m,q,w[N],las,dep[N];
int root(int x){return x==fa[x]?x:fa[x]=root(fa[x]);}
vector < pii > Q;

void Kruskal(){
	sort(a+1,a+1+m);
	for(int i=1;i<=m;++i){
		int x=root(a[i].x);
		int y=root(a[i].y);
		if(x==y) continue;
		w[++tot]=a[i].z;
		fa[x]=fa[y]=tot;
		ls[tot]=x;rs[tot]=y;
	}
}

void dfs(int x,int y){
	f[x][0]=y;dep[x]=dep[y]+1;
	for(int i=1;i<=B;++i) f[x][i]=f[f[x][i-1]][i-1];
	if(x<=n) siz[x]=1;
	else {
		dfs(ls[x],x);dfs(rs[x],x);
		siz[x]=siz[ls[x]]+siz[rs[x]];
	}
}

inline int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=B;~i;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=B;~i;--i) if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
	return f[x][0];
} 

inline int jump(int x){
	for(int i=B;~i;--i) if(f[x][i]&&w[f[x][i]]>=las) x=f[x][i];
	return siz[x];
}

int main(){
	cin>>n>>m>>q;tot=n;
	for(int i=1;i<=(n<<1);++i) fa[i]=i;
	for(int i=1;i<=m;++i) cin>>a[i].x>>a[i].y>>a[i].z;
	for(int i=1;i<=m;++i) b[i]=a[i];Kruskal();
	for(int i=tot;i;--i) if(!siz[i]) dfs(i,0);
	for(int i=1,opt,x,y;i<=q;++i){
		cin>>opt>>x;
		if(opt==1){for(auto i:Q) w[i.fi]=i.sec;Q.clear();las=x;}
		else if(opt==2) cout<<jump(x)<<endl;
		else {
			cin>>y;
			int lca=LCA(b[x].x,b[x].y);
			if(w[lca]!=b[x].z) continue;
			Q.emplace_back(lca,b[x].z=y);
		}
	}
	return 0;
}
//这条边有可能本来就没影响。输。