社区讨论

0pts为什么全部RE了!!赏关求助!

P2486[SDOI2011] 染色参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mj1duf39
此快照首次捕获于
2025/12/11 19:56
3 个月前
此快照最后确认于
2025/12/13 19:00
3 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
#define lp p<<1
#define rp p<<1|1
using namespace std;
const int N=1e5+5;
int n,m,cnt,h[N],a[N],son[N],size[N],fath[N],d[N];
int jim,dfn[N],col[N],top[N],pos1,pos2,Lc,Rc;
struct node{
	int to,nxt;
}edge[N*2];
struct tree{
	int l,r,lc,rc,num,tag;
}tr[N*4];
void add(int u,int v){
	edge[++cnt].nxt=h[u];
	edge[cnt].to=v;
	h[u]=cnt;
}
//---------------Stree
void spread(int p){
	if(tr[p].tag){
		tr[lp].num=tr[rp].num=1;
		tr[lp].lc=tr[lp].rc=tr[rp].lc=tr[rp].rc=tr[p].tag;
		tr[lp].tag=tr[rp].tag=tr[p].tag;
		tr[p].tag=0;
	}
}
void pushup(int p){
	if(tr[lp].rc!=tr[rp].lc) tr[p].num=tr[lp].num+tr[rp].num;
	else tr[p].num=tr[lp].num+tr[rp].num-1;
	tr[p].lc=tr[lp].lc;
	tr[p].rc=tr[rp].rc;
}
void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].num=1;
		tr[p].lc=tr[p].rc=col[l];
		return;
	}
	int mid=l+r>>1;
	build(lp,l,mid);
	build(rp,mid+1,r);
	pushup(p);
}
void change(int p,int l,int r,int c){
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].tag=c;
		tr[p].num=1;
		tr[p].lc=tr[p].rc=c;
		return;
	}
	spread(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid) change(lp,l,r,c);
	if(r>mid) change(rp,l,r,c);
	pushup(p);
}
int query(int p,int l,int r){
	if(tr[p].l==l) Lc=tr[p].lc;
	if(tr[p].r==r) Rc=tr[p].rc;
	if(l<=tr[p].l&&tr[p].r<=r){
		return tr[p].num;
	}
	spread(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(r<=mid)  
        return query(lp,l,r);  
    else if(l>mid)  
        return query(rp,l,r);  
    else{  
        int tot=query(lp,l,r)+query(rp,l,r);  
        if(tr[lp].rc ==tr[rp].lc)  
            tot--;
        return tot;  
    }

}
//---------Divid
void dfs(int u,int fa){
	fath[u]=fa;
	size[u]=1;
	d[u]=d[fa]+1;
	for(int i=h[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
		if(size[v]>size[son[u]]||!son[u]) son[u]=v;
		size[u]+=size[v];
	}
	
}
void divid(int u,int fa,int now){
	dfn[u]=++jim;
	col[jim]=a[u];
	top[u]=now;
	if(!son[u]) return;
	divid(son[u],u,now);
	for(int i=h[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa||v==son[u]) continue;
		divid(v,u,v);
	}
}
void treechange(int u,int v,int k){
	while(top[u]!=top[v]){
		if(d[top[u]]<d[top[v]]) swap(u,v);
		change(1,dfn[u],dfn[top[u]],k);
		u=fath[top[u]];
	}
	if(dfn[u]>dfn[v]) swap(u,v);
	change(1,dfn[u],dfn[v],k);
}
int treequery(int u,int v){
	int ans=0;
	while(top[u]!=top[v]){
		if(d[top[u]]<d[top[v]]) swap(u,v),swap(pos1,pos2);
		ans+=query(1,dfn[u],dfn[top[u]]);
		if(pos1==Rc) ans--;
		pos1=Lc;
		u=fath[top[u]];
	}
	if(dfn[u]>dfn[v]) swap(u,v),swap(pos1,pos2);
	ans+=query(1,dfn[u],dfn[v]);
	if(Rc==pos1) ans--;
	if(Lc==pos2) ans--;
	return ans;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	dfs(1,1);
	divid(1,0,1);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		char op;
		int a,b,c;
		cin>>op>>a>>b;
		if(op=='C'){
			cin>>c;
			treechange(a,b,c);
		}
		else{
			pos1=pos2=-1;
			Lc=Rc=0;
			cout<<treequery(a,b)<<'\n';
		}
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...