被邪恶 #37 测试点卡掉

是一个大测试点

题意简述

操作1 : 修改一个点的权值

操作2 : 求 $u$ 到 $v$ 任意不重复路径上的最小权值

思路同 oi-wiki (拉到最底下Codeforces #487 E. Tourists)

我的输出

1424072
6030724
1090433
13527736
1424072
1424072
1424072
1424072
6030724
1424072
1424072
2527101
2527101
2527101
...

答案的输出

1090433
1090433
1090433
1090433
1090433
1090433
1090433
1090433
1090433
1090433
1090433
1090433
1090433
1090433
...

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char C=getchar();
	while(C<'0'||C>'9'){if(C=='-')f=-1;C=getchar();}
	while(C>='0'&&C<='9')x=x*10+(C^48),C=getchar();
	return x*f;
}
inline void write(int x){
    if(x<0){putchar('-'); x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const int N = 2e5+5; 
int n,m,q,u,v,w;
char op;
vector<int>tr[N];
struct E{
	int v,nxt;
}e[N<<2];
int h[N],cnt;
void addedge(int u,int v){
	++cnt;
	e[cnt].v=v;
	e[cnt].nxt=h[u];
	h[u]=cnt;
}
int stk[N],top,dfn[N],low[N],t,tot;
int val[N];
multiset<int>S[N];
void tarjan(int u){
	dfn[u]=low[u]=++t;
	stk[++top]=u;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]==low[v]){
				++tot;
				int tp;
				while(tp=stk[top]){
					tr[tp].push_back(tot);
					tr[tot].push_back(tp);
					S[tot].insert(val[tp]);
					val[tot]=*S[tot].begin();
					//cerr<<tp<<" in "<<tot<<endl;
					if(tp==u)break;
					top--;
				}
			}
		}
		else{
			low[u]=min(low[u],dfn[v]);
		}
	}
}
int f[N],de[N],sz[N],tp[N],dft[N],id[N],times;
void dfs(int u,int fa){
	de[u]=de[fa]+1;
	sz[u]=1;
	f[u]=fa;
	if(u<=n&&fa>n){
		//cerr<<val[u]<<" into "<<fa<<endl;
		S[fa].insert(val[u]);
		val[fa]=*S[fa].begin();
	}
	for(auto v:tr[u]){
		if(v==fa)continue;
		dfs(v,u);
		sz[u]+=sz[v];
	}
}
int sgt[N<<2];
void modify(int rt,int l,int r,int p,int k){
	if(l==r){
		sgt[rt]=k;
		return;
	}
	int mid=(l+r)>>1;
	p<=mid?modify(rt<<1,l,mid,p,k):modify(rt<<1|1,mid+1,r,p,k);
	sgt[rt]=min(sgt[rt<<1],sgt[rt<<1|1]);	
}
void dfs2(int u,int fir){
	//cerr<<"order: "<<u<<" "<<fir<<endl;
	int hson=0;
	dft[u]=++times;
	id[times]=u;
	tp[u]=fir;
	modify(1,1,tot,dft[u],val[u]);
	for(auto v:tr[u]){
		if(v==f[u])continue;
		if(sz[v]>sz[hson])hson=v;
	}
	if(hson)dfs2(hson,fir);
	for(auto v:tr[u]){
		if(v==f[u]||v==hson)continue;
		dfs2(v,v);
	}
	
}
int query(int rt,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		return sgt[rt];
	}
	int mid=(l+r)>>1;
	int res=2e9;
	if(ql<=mid)res=min(res,query(rt<<1,l,mid,ql,qr));
	if(qr>mid)res=min(res,query(rt<<1|1,mid+1,r,ql,qr));
	return res;
}
int Qpath(int x,int y){
	int res=2e9;
	while(tp[x]!=tp[y]){
		if(de[tp[x]]<de[tp[y]])swap(x,y);
		res=min(res,query(1,1,tot,dft[tp[x]],dft[x]));
		x=f[tp[x]];
	}
	if(de[x]>de[y])swap(x,y);
	res=min(res,query(1,1,tot,dft[x],dft[y]));
	return res;
}
int LCA(int x,int y){
	while(tp[x]!=tp[y]){
		if(de[tp[x]]<de[tp[y]])swap(x,y);
		x=f[tp[x]];
	}
	return de[x]<de[y]?x:y;
}
signed main()
{
	memset(sgt,0x3f,sizeof(sgt));
	n=tot=read();m=read();q=read();
	for(int i=1;i<=n;i++){
		val[i]=read();
	}
	for(int i=1;i<=m;i++){
		u=read();v=read();
		addedge(u,v);
		addedge(v,u); 
	}
	tarjan(1);
	dfs(1,0);
	dfs2(1,1);
	while(q--){
		cin>>op;
		if(op=='C'){
			u=read();w=read();
			int fa=f[u];
			if(fa>n){
				S[fa].erase(S[fa].find(val[u]));
				S[fa].insert(w);
				val[fa]=*S[fa].begin();
				//cerr<<"mdy:"<<fa<<" "<<val[fa]<<endl;
				modify(1,1,tot,dft[fa],val[fa]);
			}
			val[u]=w;
			//cerr<<"mdy:"<<u<<" "<<val[u]<<endl;
			modify(1,1,tot,dft[u],val[u]);
		}
		else{
			u=read();v=read();
			int lca=LCA(u,v);
			int ans=Qpath(u,v);
			if(lca>n)ans=min(ans,val[f[lca]]);
			write(ans);
			putchar('\n');
		}
	}
 	return 0;
}