明明是裸树剖 竟然调了这么久好蛋疼 大概是自己比较水的原因吧 顺便+fastio来gangbang
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cctype>
using namespace std;const int Maxn=,Maxm=Maxn;int n,m;const int D=;
char in[D],out[D/],*I=in,*O=out;inline char gc(){
return *(I++);
}inline void pc(const char& c){
*(O++)=c;
}template <typename Q>
inline void pt(Q x){
if(x==) pc('');
if(x<) pc('-'),x=-x;
static int stk[],top;
top=;
for(;x;x/=) stk[++top] = x%;
for(int i=top;i;--i) pc(stk[i]+'');
}template <typename Q>
inline void gt(Q& x){
static char c,f;
for(c=gc(),f=;!isdigit(c);c=gc()) if(c=='-') f=;
for(x=;isdigit(c);c=gc()) x=x*+c-'';
if(f) x=-x;
}struct Data {
int l,r,num;
Data (int l=-,int r=-,int num=):l(l),r(r),num(num) {}
Data operator + (const Data& rhs)const {
if(rhs.l==- && l==- ) exit(-);
if(rhs.l==-) return *this;
if(l==-) return rhs;
return Data(l,rhs.r,num+rhs.num-(r==rhs.l));
Data ret(l,rhs.r,num+rhs.num);
if(r==rhs.l) ret.num--;
return ret;
}
Data operator ~()const {
return Data(r,l,num);
}
};int tbld[Maxn];struct SegmentTree {
Data da[Maxn*];
int tag[Maxn*];
int lft,rgt,w; SegmentTree() {
memset(tag,-,sizeof tag);
} void build(int o,int l,int r){
if(l==r) {
da[o] = Data(tbld[l],tbld[l],);
return;
}
int mid=(l+r)>>;
build(o<<,l,mid);
build(o<<|,mid+,r);
da[o] = da[o<<] + da[o<<|];
} void add(int o,int col) {
da[o]=Data(col,col,);
tag[o]=col;
} void down(int o) {
if(tag[o]==-) return;
add(o<<,tag[o]);
add(o<<|,tag[o]);
tag[o]=-;
} void pp(int l,int r=,int w=) {
lft=l,rgt=r;
this->w=w;
} void change(int o,int l,int r) {
if(lft<=l && r<=rgt) {
add(o,w);
return;
}
down(o);
int mid=(l+r)>>;
if(lft<=mid) change(o<<,l,mid);
if(mid<rgt) change(o<<|,mid+,r);
da[o]=da[o<<]+da[o<<|];
} Data query(int o,int l,int r) {
if(lft<=l && r<=rgt) {
return da[o];
}
down(o);
int mid=(l+r)>>;
if(rgt<=mid) return query(o<<,l,mid);
if(mid<lft) return query(o<<|,mid+,r);
return query(o<<,l,mid)+query(o<<|,mid+,r);
} Data query(int l,int r){
pp(l,r);
return query(,,n);
} void change2(int l,int r,int w){
pp(l,r,w);
change(,,n);
}
} seg;int fir[Maxn],next[Maxm*],en[Maxm*];
int tot=;
void Add(int from,int to) {
en[++tot] = to;
next[tot] = fir[from];
fir[from] = tot;
}int sz[Maxn],son[Maxn],fa[Maxn],dep[Maxn];void dfs(int u) {
sz[u] = ;
son[u] = ;
for(int k=fir[u]; k; k=next[k]) {
const int&v=en[k];
if(v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u]+;
dfs(v);
sz[u] += sz[v];
if(sz[v]>sz[son[u]]) son[u] = v;
}
}int top[Maxn],pos[Maxn],color[Maxn],clk=;void build(int u,int pre) {
top[u] = pre;
pos[u] = ++clk;
tbld[clk] = color[u];
if(son[u]) build(son[u],pre);
for(int k=fir[u]; k; k=next[k]) {
const int&v = en[k];
if(v==fa[u] || v==son[u]) continue;
build(v,v);
}
}void change(int a,int b,int c){
int ta=top[a],tb=top[b];
for(;ta!=tb;a=fa[ta],ta=top[a]){
if(dep[ta] < dep[tb] ) swap(a,b), swap(ta,tb);
seg.change2(pos[ta],pos[a],c);
}
if(dep[a]>dep[b]) swap(a,b);
seg.change2(pos[a],pos[b],c);
}Data query(int a,int b) {
int ta=top[a],tb=top[b]; Data res1,res2; for(;ta!=tb;){
if(dep[ta]>dep[tb]){
res1 = seg.query(pos[ta],pos[a]) + res1;//注意这里以及下面加的顺序，写的时候没想好，调了好久
a=fa[ta],ta=top[a];
} else {
res2 = seg.query(pos[tb],pos[b]) + res2;
b=fa[tb],tb=top[b];
}
}
// Data tmp ( seg.query(pos[b],pos[a]) );
if(dep[a]<dep[b]) return (~res1)+seg.query(pos[a],pos[b])+res2;//还有这里要取反各种坑，各种要注意顺序
// tmp=(~res2)+seg.query(pos[b],pos[a]);
// tmp=tmp+res1;
return (~res2)+seg.query(pos[b],pos[a])+res1;
}int main() {
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout); fread(in,,D,stdin); gt(n),gt(m); for(int i=;i<=n;i++) gt(color[i]); for(int u,v,i=;i<n;i++){
gt(u),gt(v);
Add(u,v);
Add(v,u);
} dfs();
build(,);
seg.build(,,n);// for(int i=1;i<=n;i++) printf("%d\n",son[i]);
// return 0; char cmd;
int a,b,c;// for(I=1;I<=m;I++)
for(;m--;){ /*if(I==2) {
Data tmp=seg.query( pos[2],pos[7] );
tmp=seg.query( pos[3],pos[4]);
tmp=seg.query( pos[2],pos[6]);
tmp=seg.query( pos[6],pos[7]);
I=2;
}*/ for(cmd=gc();cmd!='Q'&&cmd!='C';cmd=gc());
gt(a);gt(b);
if(cmd == 'Q') pt(query(a,b).num),pc('\n');
else gt(c), change(a,b,c);
} return printf(out),;
}
嗯，其实lct还是挺好写的，就是有点慢TAT
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
using namespace std; const int Maxn = ; int ch[Maxn][],p[Maxn],sz[Maxn],flip[Maxn],tag[Maxn];
int col[Maxn];
int n,m; const int D=;
char in[D],out[*],*I=in,*O=out;
#define gc (*I++)
#define pc(x) ((*O++)=x)
template <typename Q>
void gt(Q&x) {
static char c,f;
for(c=gc,f=;!isdigit(c);c=gc)if(c=='-') f=;
for(x=;isdigit(c);c=gc) x=x*+c-'';
f && (x=-x);
} struct Data {
int l,r,num;
Data(int l=-,int r=-,int num=):l(l),r(r),num(num) {}
Data operator + (const Data& rhs) const {
if(!num) return rhs;
if(!rhs.num) return *this;
return Data (l,rhs.r,num+rhs.num-(r==rhs.l));
}
void flip() {
swap(l,r);
}
}da[Maxn]; template <typename Q>
void pt(Q x){
static char stk[];
static int top;
top=;
if(x==) pc('');
for(;x;x/=) stk[++top] = x%+'';
for(;top;top--) pc(stk[top]);
} int fir[Maxn],next[Maxn*],en[Maxn*];
void Add(int from,int to) {
static int tot=;
en[++tot]=to;
next[tot]=fir[from];
fir[from]=tot;
} void add_tag(int x,int Col) {
if(x==) return;
col[x] = tag[x] = Col;
da[x] = Data(Col,Col,);
} void down(int x) {
if(flip[x]) {
swap(ch[x][],ch[x][]);
flip[ch[x][]]^=; da[ch[x][]].flip();
flip[ch[x][]]^=; da[ch[x][]].flip();
flip[x]=;
}
if(tag[x]!=-) {
add_tag(ch[x][],tag[x]);
add_tag(ch[x][],tag[x]);
tag[x]=-;
}
} bool isroot(int x){
return ch[p[x]][]!=x && ch[p[x]][]!=x;
} void update(int x) {
if(x==) return;
sz[x]=sz[ch[x][]]+sz[ch[x][]]+;
da[x]=da[ch[x][]]+Data(col[x],col[x],)+da[ch[x][]];
} void rotate(int x) {
int y=p[x],z=p[y];
int l=ch[y][]==x,r=l^;
if(!isroot(y)) ch[z][ch[z][]==y]=x;
p[ch[x][r]]=y;
p[y]=x;
p[x]=z; ch[y][l]=ch[x][r];
ch[x][r]=y; update(y);
update(x);
} void splay(int x){
static int stk[Maxn],top;
stk[top=]=x;
for(int t=x;!isroot(t);t=p[t]) stk[++top] = p[t];
for(;top;top--) down(stk[top]);
for(;!isroot(x);){
int y=p[x],z=p[y];
if(!isroot(y)){
if( (ch[y][]==x)^(ch[z][]==y) )
rotate(x);else rotate(y);
}
rotate(x);
}
} void access(int x){
for(int t=;x;x=p[t=x]){
splay(x);
ch[x][]=t;
update(x);
}
} int getroot(int x){
for(access(x),splay(x);ch[x][];x=ch[x][]);
return x;
} void cut(int x){
access(x);
splay(x);
p[ch[x][]]=;
ch[x][]=;
update(x);
} void combine(int x,int y) {
cut(x);
p[x]=y;
update(y);
} void newroot(int x){
access(x);
splay(x);
flip[x]^=;
da[x].flip();
} void dfs(int x) {
for(int k=fir[x];k;k=next[k]) {
int v=en[k];
if(v==p[x]) continue;
p[v]=x;
dfs(v);
}
} void init(){
gt(n);gt(m);
memset(tag,-,sizeof(*tag)*(n+));
for(int i=;i<=n;i++) {
gt(col[i]);
sz[i]=;
da[i] = Data( col[i],col[i],);
}
for(int u,v,i=;i<n;i++) {
gt(u),gt(v);
Add(u,v);
Add(v,u);
}
dfs();
} void work() {
char cmd;
int a,b,c;
for(int i=;i<=m;i++) {
for(cmd=gc;cmd!='C' && cmd!='Q';cmd=gc);
gt(a);gt(b);
newroot(a);
access(b);
splay(b);
if(cmd=='C') {
gt(c);
add_tag(b,c);
}else {
pt(da[b].num);
pc('\n');
}
}
}
int main() {
#ifdef DEBUG
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);
#endif
fread(in,,D,stdin); init();
work(); return printf(out),;
}
