/****************************************\
* Author : ztx
* Title  : [SDOI2011]染色
* ALG    : LCT
* CMT    :
* 多打打标记就好了嘛~
* Data   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [SDOI2011]染色
* ALG    : LCT
* CMT    :
* 多打打标记就好了嘛~
* Data   :
\****************************************/

#include <cstdio>

int CH ;
inline void read(int& ret) {
    ret = 0 ; while (CH=getchar() , CH<'!') ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
}

#define  maxn  100010LL
#define  maxe  200010LL

int fa[maxn] = {0} , ch[maxn][2] = {0} ;
int cover[maxn] = {0} ;
int color[maxn] = {0} , lcolor[maxn] = {0} , rcolor[maxn] = {0} , d[maxn] = {0} ;

#define  null      0LL
#define  left(u)   ch[u][0]
#define  right(u)  ch[u][1]

inline bool Isrt(int u){ return ((!fa[u])||(fa[u]&&(left(fa[u])!=u)&&(right(fa[u])!=u))) ; }
inline void Maintain(int u) {
    lcolor[u] = left(u) ? lcolor[left(u)] : color[u] ;
    rcolor[u] = right(u) ? rcolor[right(u)] : color[u] ;
    d[u] = d[left(u)]+1+d[right(u)]-(rcolor[left(u)]==color[u])-(lcolor[right(u)]==color[u]) ;
}

inline void Paint(int u , int col) {
    if (!u) return ;
    lcolor[u] = rcolor[u] = color[u] = cover[u] = col ; d[u] = 1 ;
}

inline void Clear(int u) {
	if (!u) return ;
    if (!Isrt(u)) Clear(fa[u]) ;
    if (cover[u]) {
        Paint(left(u) , cover[u]) ;
        Paint(right(u) , cover[u]) ;
        cover[u] = 0 ;
    }
}

inline void zig(int x) {
	/* right rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[right(x)] = y ; left(y) = right(x) ; fa[y] = x ; right(x) = y ;
    Maintain(y) ;
}

inline void zag(int x) {
	/* left rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[left(x)] = y ; right(y) = left(x) ; fa[y] = x ; left(x) = y ;
    Maintain(y) ;
}

inline void Splay(int x) {
    Clear(x) ;
    for (int y , z ; !Isrt(x) ; ) {
        y = fa[x] , z = fa[y] ;
        if (Isrt(y))
            if(left(y) == x) zig(x) ; else zag(x) ;
        else if(left(z) == y)
            if(left(y) == x) zig(y),zig(x) ; else zag(x),zig(x) ;
        else if(right(y) == x) zag(y),zag(x) ; else zig(x),zag(x) ;
    }
    Maintain(x) ;
}

inline void QUERY(int u , int v) {
	for (int z = null ; v ; v = fa[v] ) {
		Splay(v) ; right(v) = z , z = v ; Maintain(v) ;
	}
	for (v = null ; u ; u = fa[u]) {
    	Splay(u) ;
    	if (!fa[u]) {
			printf("%d\n", d[right(u)]+d[v]+1-(color[u]==lcolor[right(u)])-(color[u]==lcolor[v]) ) ;
            return ;
		}
		right(u) = v , v = u ; Maintain(u) ;
	}
}

inline void CHANGE(int u , int v , int w) {
	for (int z = null ; v ; v = fa[v] ) {
		Splay(v) ; right(v) = z , z = v ; Maintain(v) ;
	}
    for (v = null ; u ; u = fa[u]) {
    	Splay(u) ;
    	if (!fa[u]) {
    		color[u] = w ;
    		Paint(right(u) , w) ;
    		Paint(v , w) ;
		}
		right(u) = v , v = u ; Maintain(u) ;
	}
}

struct FST { int to , next ; } e[maxe] ;
int star[maxn] = {0} , tote = 0 ;

inline void AddEdge(int u , int v) {
    e[++tote].to = v ; e[tote].next = star[u] ; star[u] = tote ;
    e[++tote].to = u ; e[tote].next = star[v] ; star[v] = tote ;
}

inline void BuildTree(int fat , int u) {
    fa[u] = fat ; int p , v ;
    for (p = star[u] ; p ; p = e[p].next ) {
        v = e[p].to ; if (v == fat) continue ;
        BuildTree(u , e[p].to) ;
    }
}

int n , q , i , u , v , w ;

int main() {
//    #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    read(n) , read(q) ;
    for (i = 1 ; i <= n ; i ++ ) {
        read(color[i]) ; lcolor[i] = rcolor[i] = color[i] ; d[i] = 1 ;
    }
    for (i = 1 ; i < n ; i ++ ) {
        read(u) , read(v) ; AddEdge(u , v) ;
    }
    BuildTree(null , 1) ;
    while ( q -- ) {
        while (w=getchar() , w<'!') ;
        read(u) , read(v) ;
        if (w == 'Q') QUERY(u , v) ;
        else read(w) , CHANGE(u , v , w) ;
    }
	#ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

• 相关文章
• 全局相关文章