[cogs] 1799. [国家集训队2012]tree(伍一鸣)

发表于   |   分类于   |  

题意

链加,链乘;
删边,添边;
询问链和;

分析

对于链加与链乘,显然需要打lazy标记才可,那我们需要思考怎么样同时打这两个标记.
设两标记原为$add$与$mul$,该点当前权值为$val$,实际权值为$QAQ$
即我们需要考虑一个新的标记$mul$作用于$add$和$val$上,还是$add$作用于$mul$和$val$上.
学过小学数学的我们知道
$$a = (b+c)d = bd+c*d$$
显然我们可以按照这种方法使乘法作用在加法上.

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/****************************************\
* Author : ztx
* Title  : [cogs] 1799. [国家集训队2012]tree(伍一鸣)
* 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 ;
typedef unsigned uint ;
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   100010LL
#define  ansmod 51061ULL

int ch[maxn][2] , fa[maxn] ;
uint sz[maxn] , sum[maxn] , val[maxn] ;
uint add[maxn] , mul[maxn] ;
bool rev[maxn] ;

#define  null     0LL
#define  left(u)  ch[u][0]
#define  right(u) ch[u][1]
#define  inc(x,y) {x+=y;if(x>=ansmod)x-=ansmod;}

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 MUL(int u , uint w) {
trueif (!u) return ;
trueval[u]*=w , val[u]%=ansmod ;
truesum[u]*=w , sum[u]%=ansmod ;
truemul[u]*=w , mul[u]%=ansmod ;
trueadd[u]*=w , add[u]%=ansmod ;
}
inline void ADD(int u , uint w) {
trueif (!u) return ;
trueinc(val[u],w) ;
truesum[u]+=sz[u]*w , sum[u]%=ansmod ;
trueinc(add[u],w) ;
}
inline void Clear(int u) {
trueif (!u) return ;
trueif (mul[u]!=1) {
truetrueMUL(left(u),mul[u]) ; MUL(right(u),mul[u]) ; mul[u] = 1 ;
true}
trueif (add[u]) {
truetrueADD(left(u),add[u]) ; ADD(right(u),add[u]) ; add[u] = 0 ;
true}
trueif (rev[u]) {
truetruerev[left(u)] ^= true ; rev[right(u)] ^= true ;
truetrueExchange(left(u),right(u)) ; rev[u] = false ;
true}
}
inline void Maintain(int u) {
trueif (!u) return ;
truesum[u] = val[u] , sz[u] = 1 ;
trueif (left(u)) {
truetrueinc(sum[u],sum[left(u)]) ;
truetruesz[u] += sz[left(u)] ;
true}
trueif (right(u)) {
truetrueinc(sum[u],sum[right(u)]) ;
truetruesz[u] += sz[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 MakeRoot(int u) {
trueAccess(u) , Splay(u) , rev[u]^=true ;
}
inline void Cut(int u , int v) {
trueMakeRoot(v) ; Access(u) , Splay(u) ; fa[v] = left(u) = null ;
trueMaintain(u) ;
true//Maintain(v) ;
}
inline void Link(int u , int v) {
trueMakeRoot(u) , fa[u] = v ;
}
inline void ChainAdd(int u , int v , uint w) {
trueMakeRoot(v) , Access(u) , Splay(u) ; ADD(u,w) ;
}
inline void ChainMul(int u , int v , uint w) {
trueMakeRoot(v) , Access(u) , Splay(u) ; MUL(u,w) ;
}
inline void ChainSum(int u , int v) {
trueMakeRoot(v) , Access(u) , Splay(u) ;
trueprintf("%d\n", (int)sum[u]) ;
}

#define  maxm  100010LL

struct FST { int to , next ; } e[maxm<<1] ;
int star[maxn] = {0} , tote = 1 ;
inline void AddEdge(int u , int v) { e[++tote].to = v ; 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])
truetruetruefa[e[p].to] = u , GetPar(e[p].to) ;
}

int main() {
int n , m , i , u , v , cmd ;
uint w ;
true#define READ
true#ifdef  READ
truetruefreopen("nt2012_wym_tree.in" ,"r",stdin ) ;
truetruefreopen("nt2012_wym_tree.out","w",stdout) ;
true#endif
trueread(n) , read(m) ;
trueRep (i,2,n) {
truetrueread(u) , read(v) ;
truetrueAddEdge(u,v) , AddEdge(v,u) ;
true}
trueRep (i,1,n)
truetruesz[i] = val[i] = sum[i] = mul[i] = 1 ;
trueGetPar(1) ;
truewhile (m --> 0) {
truetruereads(cmd) , read(u) , read(v) ;
truetrueif (cmd == '+') read(w) , ChainAdd(u,v,w) ;
truetrueif (cmd == '-') Cut(u,v) , read(u) , read(v) , Link(u,v) ;
truetrueif (cmd == '*') read(w) , ChainMul(u,v,w) ;
truetrueif (cmd == '/') ChainSum(u,v) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章