HDU5002:Tree(LCT)

Description

Input

Output

Sample Input

Sample Output

Solution

写了$6k$有点自闭……
一操作加边断边，二操作路径覆盖，三操作路径加，四操作求路径次大值和次大值个数。
记得讨论好覆盖标记和加标记的关系……再维护下最大值，最大值个数，次大值和次大值个数就好了。
码农题也没什么好说的……
Code

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #define N (100009)
  5 #define INF (2000000000)
  6 using namespace std;
  7 
  8 int T,n,m,a,b,x,y,opt;
  9 int Max1[N],Max2[N],Cnt1[N],Cnt2[N],Rev[N],Val[N];
 10 int Father[N],Son[N][2],Add[N],Cov[N],Size[N];
 11 
 12 inline int read()
 13 {
 14     int x=0,w=1; char c=getchar();
 15     while (c<'0' || c>'9') {if (c=='-') w=-1; c=getchar();}
 16     while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();
 17     return x*w;
 18 }
 19 
 20 int Get(int x)
 21 {
 22     return Son[Father[x]][1]==x;
 23 }
 24 
 25 int Is_root(int x)
 26 {
 27     return Son[Father[x]][0]!=x && Son[Father[x]][1]!=x;
 28 }
 29 
 30 void Pushup(int x)
 31 {
 32     Size[x]=Size[Son[x][0]]+Size[Son[x][1]]+1;
 33     if (!Son[x][0] && !Son[x][1])
 34     {
 35         Max1[x]=Val[x]; Max2[x]=-INF;
 36         Cnt1[x]=1; Cnt2[x]=0;
 37         return;
 38     }
 39     if (!Son[x][1])
 40     {
 41         Max1[x]=Max1[Son[x][0]]; Max2[x]=Max2[Son[x][0]];
 42         Cnt1[x]=Cnt1[Son[x][0]]; Cnt2[x]=Cnt2[Son[x][0]];
 43     }
 44     else if (!Son[x][0])
 45     {
 46         Max1[x]=Max1[Son[x][1]]; Max2[x]=Max2[Son[x][1]];
 47         Cnt1[x]=Cnt1[Son[x][1]]; Cnt2[x]=Cnt2[Son[x][1]];
 48     }
 49     else if (Max1[Son[x][0]]==Max1[Son[x][1]])
 50     {
 51         Max1[x]=Max1[Son[x][0]];
 52         Cnt1[x]=Cnt1[Son[x][0]]+Cnt1[Son[x][1]];
 53         if (Max2[Son[x][0]]==Max2[Son[x][1]])
 54             Max2[x]=Max2[Son[x][0]], Cnt2[x]=Cnt2[Son[x][0]]+Cnt2[Son[x][1]];
 55         else if (Max2[Son[x][0]]>Max2[Son[x][1]])
 56             Max2[x]=Max2[Son[x][0]], Cnt2[x]=Cnt2[Son[x][0]];
 57         else Max2[x]=Max2[Son[x][1]], Cnt2[x]=Cnt2[Son[x][1]];
 58     }
 59     else if (Max1[Son[x][0]]>Max1[Son[x][1]])
 60     {
 61         Max1[x]=Max1[Son[x][0]];
 62         Cnt1[x]=Cnt1[Son[x][0]];
 63         if (Max2[Son[x][0]]==Max1[Son[x][1]])
 64             Max2[x]=Max2[Son[x][0]], Cnt2[x]=Cnt2[Son[x][0]]+Cnt1[Son[x][1]];
 65         else if (Max2[Son[x][0]]>Max1[Son[x][1]])
 66             Max2[x]=Max2[Son[x][0]], Cnt2[x]=Cnt2[Son[x][0]];
 67         else Max2[x]=Max1[Son[x][1]], Cnt2[x]=Cnt1[Son[x][1]];
 68     }
 69     else
 70     {
 71         Max1[x]=Max1[Son[x][1]];
 72         Cnt1[x]=Cnt1[Son[x][1]];
 73         if (Max1[Son[x][0]]==Max2[Son[x][1]])
 74             Max2[x]=Max1[Son[x][0]], Cnt2[x]=Cnt1[Son[x][0]]+Cnt2[Son[x][1]];
 75         else if (Max1[Son[x][0]]>Max2[Son[x][1]])
 76             Max2[x]=Max1[Son[x][0]], Cnt2[x]=Cnt1[Son[x][0]];
 77         else Max2[x]=Max2[Son[x][1]], Cnt2[x]=Cnt2[Son[x][1]];
 78     }
 79     if (Val[x]>Max1[x])
 80     {
 81         Cnt2[x]=Cnt1[x]; Max2[x]=Max1[x];
 82         Cnt1[x]=1; Max1[x]=Val[x];
 83     }
 84     else if (Val[x]==Max1[x]) Cnt1[x]++;
 85     else if (Val[x]>Max2[x]) Max2[x]=Val[x], Cnt2[x]=1;
 86     else if (Val[x]==Max2[x]) Cnt2[x]++;
 87 }
 88 
 89 void Pushdown(int x)
 90 {
 91     if (Rev[x])
 92     {
 93         if (Son[x][0]) Rev[Son[x][0]]^=1;
 94         if (Son[x][1]) Rev[Son[x][1]]^=1;
 95         swap(Son[x][0],Son[x][1]);
 96         Rev[x]=0;
 97     }
 98     if (Add[x])
 99     {
100         if (Son[x][0])
101         {
102             Val[Son[x][0]]+=Add[x];
103             Add[Son[x][0]]+=Add[x];
104             Max1[Son[x][0]]+=Add[x];
105             if (Cov[Son[x][0]]!=INF) Cov[Son[x][0]]+=Add[x];
106             if (Max2[Son[x][0]]!=-INF) Max2[Son[x][0]]+=Add[x];
107         }
108         if (Son[x][1])
109         {
110             Val[Son[x][1]]+=Add[x];
111             Add[Son[x][1]]+=Add[x];
112             Max1[Son[x][1]]+=Add[x];
113             if (Cov[Son[x][1]]!=INF) Cov[Son[x][1]]+=Add[x];
114             if (Max2[Son[x][1]]!=-INF) Max2[Son[x][1]]+=Add[x];
115         }
116         Add[x]=0;
117     }
118     if (Cov[x]!=INF)
119     {
120         if (Son[x][0])
121         {
122             Val[Son[x][0]]=Cov[x];
123             Add[Son[x][0]]=0;
124             Cov[Son[x][0]]=Cov[x];
125             Max1[Son[x][0]]=Cov[x];
126             Max2[Son[x][0]]=-INF;
127             Cnt1[Son[x][0]]=Size[Son[x][0]];
128             Cnt2[Son[x][0]]=0;
129         }
130         if (Son[x][1])
131         {
132             Val[Son[x][1]]=Cov[x];
133             Add[Son[x][1]]=0;
134             Cov[Son[x][1]]=Cov[x];
135             Max1[Son[x][1]]=Cov[x];
136             Max2[Son[x][1]]=-INF;
137             Cnt1[Son[x][1]]=Size[Son[x][1]];
138             Cnt2[Son[x][1]]=0;
139         }
140         Cov[x]=INF;
141     }
142 }
143 
144 void Rotate(int x)
145 {
146     int wh=Get(x);
147     int fa=Father[x],fafa=Father[fa];
148     if (!Is_root(fa)) Son[fafa][Son[fafa][1]==fa]=x;
149     Father[fa]=x; Son[fa][wh]=Son[x][wh^1];
150     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
151     Father[x]=fafa; Son[x][wh^1]=fa;
152     Pushup(fa); Pushup(x);
153 }
154 
155 void Push(int x)
156 {
157     if (!Is_root(x)) Push(Father[x]);
158     Pushdown(x);
159 }
160 
161 void Splay(int x)
162 {
163     Push(x);
164     for (int fa; !Is_root(x); Rotate(x))
165         if (!Is_root(fa=Father[x]))
166             Rotate(Get(fa)==Get(x)?fa:x);
167 }
168 
169 void Access(int x)
170 {
171     for (int y=0; x; y=x,x=Father[x])
172         Splay(x), Son[x][1]=y, Pushup(x);
173 }
174 
175 void Make_root(int x)
176 {
177     Access(x); Splay(x);
178     Rev[x]^=1;
179 }
180 
181 int Find_root(int x)
182 {
183     Access(x); Splay(x);
184     while (Son[x][0]) x=Son[x][0];
185     return x;
186 }
187 
188 void Link(int x,int y)
189 {
190     Make_root(x);
191     Father[x]=y;
192 }
193 
194 void Cut(int x,int y)
195 {
196     Make_root(x);
197     Access(y); Splay(y);
198     Father[x]=Son[y][0]=0;
199     Pushup(y);
200 }
201 
202 void Clear()
203 {
204     memset(Max1,0,sizeof(Max1));
205     memset(Max2,0,sizeof(Max2));
206     memset(Cnt1,0,sizeof(Cnt1));
207     memset(Cnt2,0,sizeof(Cnt2));
208     memset(Father,0,sizeof(Father));
209     memset(Son,0,sizeof(Son));
210     memset(Cov,0,sizeof(Cov));
211     memset(Add,0,sizeof(Add));
212     memset(Size,0,sizeof(Size));
213 }
214 
215 int main()
216 {
217     T=read();
218     for (int t=1; t<=T; ++t)
219     {
220         Clear();
221         n=read(); m=read();
222         for (int i=1; i<=n; ++i)
223         {
224             Val[i]=read();
225             Max1[i]=Val[i]; Cnt1[i]=1; Size[i]=1;
226             Cov[i]=INF; Max2[i]=-INF;
227         }
228         for (int i=1; i<=n-1; ++i)
229             x=read(), y=read(), Link(x,y);
230         printf("Case #%d:
",t);
231         for (int i=1; i<=m; ++i)
232         {
233             opt=read();
234             if (opt==1)
235             {
236                 x=read(); y=read(); a=read(); b=read();
237                 Cut(x,y); Link(a,b);
238             }
239             if (opt==2)
240             {
241                 a=read(); b=read(); x=read();
242                 Make_root(a); Access(b); Splay(b);
243                 Cov[b]=x; Add[b]=0; Val[b]=x;
244                 Max2[b]=-INF; Cnt2[b]=0;
245                 Max1[b]=x; Cnt1[b]=Size[b];
246             }
247             if (opt==3)
248             {
249                 a=read(); b=read(); x=read();
250                 Make_root(a);
251                 Access(b);
252                 Splay(b);
253                 Add[b]+=x; Val[b]+=x; Max1[b]+=x;
254                 if (Cov[b]!=INF) Cov[b]+=x;
255                 if (Max2[b]!=-INF) Max2[b]+=x;
256             }
257             if (opt==4)
258             {
259                 a=read(); b=read();
260                 Make_root(a);
261                 Access(b);
262                 Splay(b);
263                 if (!Cnt2[b]) puts("ALL SAME");
264                 else printf("%d %d
",Max2[b],Cnt2[b]);
265             }
266         }
267     }
268 }