/****************************************\
* Author : ztx
* Title  : [POJ3237]树的维护
* ALG    : LCT
* CMT    :
* 很明显的动态树模型, 首先要把边权转化为点权,
* 并且要在dfs的时候记录每条边的权值在哪个点里面.
* 操作1 和3 是常规操作.
* 对于操作2, 我们对每个节点记录Max和Min, 取反就等价于Max = -Min , Min = -Max
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [POJ3237]树的维护
* ALG    : LCT
* CMT    :
* 很明显的动态树模型, 首先要把边权转化为点权,
* 并且要在dfs的时候记录每条边的权值在哪个点里面.
* 操作1 和3 是常规操作.
* 对于操作2, 我们对每个节点记录Max和Min, 取反就等价于Max = -Min , Min = -Max
* Time   :
\****************************************/

#include <cstdio>
#include <cstring>

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 ;
}

inline void reads(int& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}

#define  maxn     10010LL
#define  maxe     20010LL
#define  infi     0x7f7f7f7fLL
#define  max(a,b) ((a)>(b)?(a):(b))
#define  min(a,b) ((a)<(b)?(a):(b))

struct FST { int to , next , val ; } e[maxe] ;
int star[maxn] = {0} , tote = 1 ;/* ! */
void AddEdge(int u , int v , int w) {
	e[++tote].to = v ; e[tote].val = w ; e[tote].next = star[u] ; star[u] = tote ;
	e[++tote].to = u ; e[tote].val = w ; e[tote].next = star[v] ; star[v] = tote ;
}

int fa[maxn] = {0} , ch[maxn][2] = {0} ;
int val[maxn] = {0} , maxv[maxn] = {0} , minv[maxn] = {0} ;
bool neg[maxn] = {0} ;

int belong[maxn] = {0} ;

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

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

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

inline void Negated(int u) {
	if (u) {
		neg[u] ^= true ;
		val[u] = -val[u] ;
		maxv[u] = -maxv[u] ;
		minv[u] = -minv[u] ;
		Exchange(maxv[u] , minv[u]) ;
	}
}

inline void Clear(int u) {
	if (u && neg[u]) {
		Negated(left(u)) ;
		Negated(right(u)) ;
		neg[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) ; Clear(u) ;
		right(u) = v , v = u ; Maintain(u) ;
	}
}

int vis[maxn] = {0} ;
void Build(int u) {
	vis[u] = true ;
	int p , v ;
	for (p=star[u] ; p ; p =e[p].next) {
		v = e[p].to ;
		if (vis[v]) fa[u] = v ;
		else {
			val[v] = e[p].val ;
			belong[p>>1] = v ;
			Build(v) ;
		}
	}
}

void CHANGE(int u , int w) {
	u = belong[u] ; Splay(u) ; val[u] = w ;
}

void NEGATE(int u , int v) {
	Access(v) ;
	for (v = null ; u ; u = fa[u]) {
		Splay(u) ;
		if (!fa[u]) {
			Negated(v) , Negated(right(u)) ;
			return ;
		}
		Clear(u) ;
		right(u) = v , v = u ; Maintain(u) ;
	}
}

void QUERY(int u , int v) {
	Access(v) ;
	for (v = null ; u ; u = fa[u]) {
		Splay(u) ;
		if (!fa[u]) {
			printf("%d\n", max(maxv[v] , maxv[right(u)])) ;
			return ;
		}
		Clear(u) ;
		right(u) = v , v = u ; Maintain(u) ;
	}
}

int n , i , u , v , w ;

int main() {
    #define READ
    #ifdef  READ
        freopen("maintaintree.in" ,"r",stdin ) ;
        freopen("maintaintree.out","w",stdout) ;
    #endif
    read(n) ;
    for (i = 1 ; i < n ; i ++ ) {
    	read(u) , read(v) , read(w) ;
    	AddEdge(u , v , w) ;
	}
	maxv[null] = -infi , minv[null] = infi ;
	Build(1) ;
	while (reads(i) , i!='D') {
		read(u) , read(v) ;
		if (i == 'C') CHANGE(u , v) ;
		if (i == 'Q') QUERY(u , v) ;
		if (i == 'N') NEGATE(u , v) ;
	}
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

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