[cogs] 1583. [POJ3237]树的维护

发表于   |   分类于   |  

题意

点修改,链上边权取反;
询问链上边权最大值.

分析

我们把边权存在点上,在建立边与点的对应关系,就可以进行点修改了.
那么我们要修改和查询关于链上的边权又要怎么办呢?
我们注意到如果进行换根操作就不能进行关于链上边权的操作了(这个画画图就能看出来)
所以我们需要一种不用换根的方法.

对于一条链$(u,v)$,首先,$Access(v)$,就会出现下图:

其中$v$与$Root$在同一棵辅助树中
再$Access(u)$,直到这种情况:

那么我们的链的边权实际上存在$b$所在的子树,$right(c)$所在的子树中.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/****************************************\
* Author : ztx
* Title  : [cogs] 1583. [POJ3237]树的维护
* ALG    : LCT复习
* CMT    :
链上边权最大值
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& 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 ;
}
template <typename TP>inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#define  maxn  10010LL

int fa[maxn] , ch[maxn][2] ;
int val[maxn] , maxv[maxn] , minv[maxn] ;
bool rev[maxn] ;

#define  null     0LL
#define  left(u)  ch[u][0]
#define  right(u) ch[u][1]
#define  max(x,y) ((x)>(y)?(x):(y))
#define  min(x,y) ((x)<(y)?(x):(y))
#define  infi     0x7f7f7f7fLL

inline void Exchange(int&a,int&b) {int c=a;a=b;b=c;}
inline bool Isrt(int u) { return !fa[u]||(left(fa[u])!=u&&right(fa[u])!=u) ; }
inline void Reverse(int u) {
trueif (!u) return ;
truerev[u]^=true , val[u]=-val[u] ;
trueExchange(maxv[u],minv[u]) , maxv[u]=-maxv[u] , minv[u]=-minv[u] ;
}
inline void Clear(int u) {
trueif (!u || !rev[u]) return ;
truerev[u] = false , Reverse(left(u)) , Reverse(right(u)) ;
}
inline void Maintain(int u) {
truemaxv[u] = minv[u] = val[u] ;
trueif (left(u)) {
truetruemaxv[u] = max(maxv[u],maxv[left(u)]) ;
truetrueminv[u] = min(minv[u],minv[left(u)]) ;
true}
trueif (right(u)) {
truetruemaxv[u] = max(maxv[u],maxv[right(u)]) ;
truetrueminv[u] = min(minv[u],minv[right(u)]) ;
true}
}
inline void Rot(int x , int d) {
trueint y=fa[x] , z=fa[y] ;
trueif (left(z)==y) left(z)=x;
trueelse if (right(z)==y) right(z)=x;
truefa[x]=z,fa[y]=x,fa[ch[x][d]]=y;
truech[y][!d]=ch[x][d],ch[x][d]=y;
trueMaintain(y) ;
}
inline void Splay(int x) {
int y , z ;
trueClear(x) ;
truewhile (!Isrt(x)) {
truetruey=fa[x] , z=fa[y] ;
truetrueClear(z) , Clear(y) , Clear(x) ;
truetrueif (Isrt(y)) Rot(x,left(y)==x) ;
truetrueelse if (left(z)==y) {
truetruetrueif (left(y)==x) Rot(y,1) ;
truetruetrueelse Rot(x,0) ; Rot(x,1) ;
truetrue} else {
truetruetrueif (right(y)==x) Rot(y,0) ;
truetruetrueelse Rot(x,1) ; Rot(x,0) ;
truetrue}
true}
trueMaintain(x) ;
}
inline void Access(int u) {
truefor (int v=null;u;v=u,u=fa[u]) Splay(u),right(u)=v,Maintain(u) ;
}
inline void NodeChange(int u , int w) {
trueSplay(u) , val[u] = w ; Maintain(u) ;
}
inline void ChainRev(int u , int v) {
truefor (Access(v),v=null;u;v=u,u=fa[u]) {
truetrueSplay(u) ;
truetrueif (!fa[u])
truetruetrueReverse(v) , Reverse(right(u)) ;
truetrueright(u)=v , Maintain(u) ;
true}
}
inline void ChainMax(int u , int v) {
truefor (Access(v),v=null;u;v=u,u=fa[u]) {
truetrueSplay(u) ;
truetrueif (!fa[u])
truetruetrueprintf("%d\n", max(maxv[v],maxv[right(u)])) ;
truetrueright(u)=v , Maintain(u) ;
true}
}

#define  maxm  10010LL
int belong[maxm] = {0} ;
struct FST { int to , next , len ; } e[maxm<<1] ;
int star[maxn] = {0} , tote = 1 ;
inline void AddEdge(int u , int v , int w) { e[++tote].to = v ; e[tote].len = w ; e[tote].next = star[u] ; star[u] = tote ; }
inline void GetPar(int u) {
truefor (int p=star[u] ; p ; p=e[p].next)
truetrueif (e[p].to != fa[u]) {
truetruetruebelong[p>>1] = e[p].to ;
truetruetruemaxv[e[p].to] = minv[e[p].to] = val[e[p].to] = e[p].len ;
truetruetruefa[e[p].to] = u ;
truetruetrueGetPar(e[p].to) ;
truetrue}
}

int main() {
int n , m , i , u , v , w , cmd ;
true#define READ
true#ifdef  READ
truetruefreopen("maintaintree.in" ,"r",stdin ) ;
truetruefreopen("maintaintree.out","w",stdout) ;
true#endif
trueread(n) ;
trueRep (i,2,n) {
truetrueread(u) , read(v) , read(w) ;
truetrueAddEdge(u,v,w) ;
truetrueAddEdge(v,u,w) ;
true}
truemaxv[null] = -infi ;
trueminv[null] = infi ;
true/*   QAQ我特么又犯了一遍这个错   */
trueGetPar(1) ;
truewhile (true) {
truetruereads(cmd) ;
truetrueif (cmd == 'D') break ;
truetrueread(u) , read(v) ;
truetrueif (cmd == 'C') NodeChange(belong[u],v) ;
truetrueif (cmd == 'Q') ChainMax(u,v) ;
truetrueif (cmd == 'N') ChainRev(u,v) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章