/****************************************\
* Author : ztx
* Title  : [ZJOI2008]树的统计Count
* ALG    : LCT
* CMT    : Link Cut Tree 的经典操作
* Data   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [ZJOI2008]树的统计Count
* ALG    : LCT
* CMT    : Link Cut Tree 的经典操作
* Data   :
\****************************************/

#include <cstdio>
#include <cstring>

#define  max(a,b)  ((a)>(b)?(a):(b))
#define  infi  0x7f7f7f7fLL

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

#define  maxn  300010LL
#define  maxe  600010LL

int fa[maxn] = {0} , ch[maxn][2] = {0} ;
int rev[maxn] = {0} ;
int maxv[maxn] , sumv[maxn] = {0} , val[maxn] = {0} ;

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

template<typename T>inline void Exchange(T&a , T&b) { T c = a ; a = b ; b = c ; }

inline bool Isrt(int u) {
	return (!fa[u]) || ((left(fa[u])!=u)&&(right(fa[u])!=u)) ;
}

inline void Maintain(int u) {
    maxv[u] = sumv[u] = val[u] ;
    if (left(u))  maxv[u] = max(maxv[u] , maxv[left(u)])  , sumv[u] += sumv[left(u)]  ;
    if (right(u)) maxv[u] = max(maxv[u] , maxv[right(u)]) , sumv[u] += sumv[right(u)] ;
}

inline void Clear(int u) {
    if (u && rev[u]) {
        if (left(u))  rev[left(u)]  ^= true ;
        if (right(u)) rev[right(u)] ^= true ;
        Exchange(left(u) , right(u)) ;
        rev[u]  = false ;
    }
}

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) ;
	int y , z ;
	while (!Isrt(x)) {
		y = fa[x] , z = fa[y] ;
		if (Isrt(y)) {
			Clear(y) , Clear(x) ;
			if (left(y) == x) zig(x) ; else zag(x) ;
		} else {
			Clear(z) , Clear(y) , Clear(x) ;
			if (left(z) == y) {
				if (left(y) == x) zig(x) , zig(x) ;
				else zag(x) , zig(x) ;
			} else if (right(z) == y) {
				if (right(y) == x) zag(x) , zag(x) ;
				else zig(x) , zag(x) ;
			}
		}
	}
	Maintain(x) ;
}

inline void Access(int u) {
	for (int v = null ; u ; u = fa[u]) Splay(u) , right(u) = v , v = u , Maintain(u) ;
}

inline void MakeRoot(int u) {
	Access(u) , Splay(u) , rev[u] ^= true ;
}

inline void QMAX(int u , int v) {
    MakeRoot(u) ; Access(v) , Splay(v) ;
    printf("%d\n", maxv[v] ) ;
}

inline void QSUM(int u , int v) {
    MakeRoot(u) ; Access(v) , Splay(v) ;
    printf("%d\n", sumv[v] ) ;
}

inline void CHANGE(int u , int v) {
    Splay(u) ; val[u] = v ; 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 tp , int u) {
int p , v ;
    fa[u] = tp ;
    for (p = star[u] ; p ; p = e[p].next ) {
        v = e[p].to ; if (v == tp) continue ;
        BuildTree(u , v) ;
    }
}

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

int main() {
    #define READ
    #ifdef  READ
        freopen("bzoj_1036.in" ,"r",stdin ) ;
        freopen("bzoj_1036.out","w",stdout) ;
    #endif
    read(n) ;
    for (i = 1 ; i < n ; i ++ ) {
        read(u) , read(v) ; AddEdge(u , v) ;
    }
    for (i = 1 ; i <= n ; i ++ )
        read(val[i]) , maxv[i] = sumv[i] = val[i] ;
    BuildTree(null , 1) ;
    read(q) ;
    while ( q -- ) {
        while (CH = getchar() , CH<'!') ;
        while (cmd = CH , CH = getchar() , CH>'!') ;
        read(u) , read(v) ;
        if (cmd == 'X') QMAX(u , v) ;
        if (cmd == 'M') QSUM(u , v) ;
        if (cmd == 'E') CHANGE(u , v) ;
    }

    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

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