社区讨论
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 条回复,欢迎继续交流。
正在加载回复...