F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
大视野在线测评-欢迎您
[ New Thread ]
Problem 2243 >> 一直RE怎么破
mk545851953 @ 2017-12-08 10:13:24
[ Quote ] [ Edit ] [ Delete ] 1#
求助,听说数据范围30w?开到30w没a
luoguAC
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300000+10;
struct node{
int cnum,cl,cr;
int lazy;
node(){
cnum=0;
cl=cr=lazy=-1;
}
}nd[maxn*8];
int top[maxn],size[maxn],son[maxn];
int fa[maxn],dep[maxn],tid[maxn];
int td=0;
vector<int>A[maxn];
int color[maxn];
int num[maxn];
int n;
inline void dfs1(int x,int d,int f){
dep[x]=d;
size[x]=1;
fa[x]=f;
for(int i=0;i<A[x].size();i++){
int u=A[x][i];
if(u==f)
continue;
dfs1(u,d+1,x);
size[x]+=size[u];
if(size[son[x]]<size[u])
son[x]=u;
}
}
inline void dfs2(int x,int tp){
tid[x]=++td;
top[x]=tp;
if(!son[x])
return ;
dfs2(son[x],tp);
for(int i=0;i<A[x].size();i++){
int u=A[x][i];
if(u==fa[x]||u==son[x])
continue;
dfs2(u,u);
}
}
inline void pushdown(int o){
if(nd[o].lazy!=-1){
nd[o<<1].cnum=nd[o<<1|1].cnum=1;
nd[o<<1].cl=nd[o<<1].cr=nd[o<<1|1].cl=nd[o<<1|1].cr=nd[o].lazy;
nd[o<<1].lazy=nd[o<<1|1].lazy=nd[o].lazy;
nd[o].lazy=-1;
}
}
inline void pushup(int o){
nd[o].cl=nd[o<<1].cl,nd[o].cr=nd[o<<1|1].cr;
nd[o].cnum=nd[o<<1].cnum+nd[o<<1|1].cnum-(nd[o<<1].cr==nd[o<<1|1].cl);
}
inline void change(int o,int l,int r,int L,int R,int x){
pushdown(o);
if(L<=l&&r<=R){
nd[o].lazy=x;
nd[o].cl=nd[o].cr=x;
nd[o].cnum=1;
return ;
}
else {
int mid=(l+r)>>1;
if(mid>=L)
change(o<<1,l,mid,L,R,x);
if(mid<R)
change(o<<1|1,mid+1,r,L,R,x);
pushup(o);
}
}
inline void build(int o,int l,int r){
if(l==r){
nd[o].cl=nd[o].cr=num[l];
nd[o].lazy=-1,nd[o].cnum=1;
return ;
}
else {
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
}
inline node query(int o,int l,int r,int L,int R){
pushdown(o);
if(L<=l&&r<=R)
return nd[o];
else {
int mid=(l+r)>>1;
node ll,rr,ans;
if(mid>=L){
ll=query(o<<1,l,mid,L,R);
ans.cnum+=ll.cnum;
ans.cl=ll.cl;
ans.cr=ll.cr;
}
if(mid<R){
rr=query(o<<1|1,mid+1,r,L,R);
ans.cnum+=rr.cnum;
if(ans.cl==-1)
ans.cl=rr.cl;
ans.cr=rr.cr;
}
if(ll.cnum&&rr.cnum){
if(ll.cr==rr.cl)
ans.cnum--;
}
return ans;
}
}
inline int Query(int x,int y){
int ans=0;
int lstx=-1,lsty=-1;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
swap(x,y);
swap(lstx,lsty);
}
node ndd=query(1,1,n,tid[top[x]],tid[x]);
ans+=ndd.cnum;
if(lstx!=-1){
if(ndd.cr==lstx)
ans--;
}
lstx=ndd.cl;
x=fa[top[x]];
}
if(dep[x]>dep[y]){
swap(x,y);
swap(lstx,lsty);
}
node ndd=query(1,1,n,tid[x],tid[y]);
ans+=ndd.cnum;
if(lsty!=-1){
if(ndd.cr==lsty)
ans--;
}
if(lstx!=-1){
if(ndd.cl==lstx)
ans--;
}
return ans;
}
inline void Change(int x,int y,int z){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
change(1,1,n,tid[top[x]],tid[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
change(1,1,n,tid[x],tid[y],z);
}
int main(){
//int size = 50 << 20;
//char *p = (char*)malloc(size) + size;
//__asm__("movl %0, %%esp\n" :: "r"(p));
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&color[i]);
int x,y;
for(int i=1;i<n;i++){
scanf("%d %d",&x,&y);
A[x].push_back(y);
A[y].push_back(x);
}
dfs1(1,1,1);
dfs2(1,1);
for(int i=1;i<=n;i++)
num[tid[i]]=color[i];
build(1,1,n);
char c;
int z;
while(m--){
cin>>c;
if(c=='C'){
scanf("%d %d %d",&x,&y,&z);
Change(x,y,z);
}
else {
scanf("%d %d",&x,&y);
printf("%d\n",Query(x,y));
}
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back