ZJOI2018历史

好久没写数据结构了,LCT都不会了

ZJOI2018历史

链接

设$v_x$为$x$的崛起次数,$s_x$为$x$及其子树的$v_x$之和,$son_x$表示$x$的儿子,$fa_x$表示$x$的父亲

先不管修改

考虑对每一个点$x​$计算贡献。

可以发现,只有当两次崛起来自于$x$的不同子树时才会产生贡献,然后考虑如何构造,对于一个点$x$,肯定把来自不同子树的崛起放在相邻位置最优。

那么如何计算一个$x​$的答案,就相当计算($a_i​$为$sz_{son_x}​$或$v_x​$)

​ 一共有m个不同色球,每种球有$a_i​$个,一共有$s​$个球把这些球排成一列,最大化$\sum\limits_{i=1}^s [col_i!=col_{i-1}]​$(中括号表示条件真时值为$1​$否则为$0​$)

然后发现$ans=min\{s-1,(s-max\{a_i\})*2\}$不会证,自己yy一下吧

然后直接$dfs$一遍就可以算出每个点的$ans$了

有了修改怎么办

先求出开始的答案,计算每次修改产生的改变

考虑上面那个柿子在何时取到后半部分,设$mx=max\{a_i\}$,取到后半部分时$mx*2>=s+1$

然后用一种神仙的$LCT$方法来维护

考虑若$sz_x*2>sz_{fa_x}$时$fa_x$向$x$连一条重链,否则连轻边。

因为当在重链上跳时,不会修改答案

只有跳到轻边时才会修改答案。

用$LCT$维护这个东西,重链在$splay$上条,轻边暴力跳,并修改轻重链信息,当每次跳一条轻边时$sz$会增大一倍,所以轻边最多跳$log_2\ sz_1$次,复杂度大概为$nlogn$。

一些实现相关

关于$LCT$维护$sz$,可以在$LCT$上把轻边信息也维护上,在修改轻重链时是有点细节

代码

这份代码好像有点锅,开了$O_2$会$RE$,不开$O2$就好了(雾

如果有大爷知道哪里锅了,欢迎私聊

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
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/03/15
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<ctime>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd() {
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=-1;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f*_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 400005
ll s[maxn],lv[maxn],val[maxn];
ll ans;
int ch[2][maxn],fa[maxn];
inline bool isroot(int x) {return !(ch[0][fa[x]]==x||ch[1][fa[x]]==x);}
#define rs (ch[1][x])
#define ls (ch[0][x])
inline void pushup(int x) {s[x]=s[ls]+s[rs]+val[x]+lv[x];}
void rotate(int x) {
int y=fa[x],z=fa[y],d=ch[1][y]==x;
if (!isroot(y)) ch[ch[1][z]==y][z]=x;
fa[y]=x,fa[x]=z;
fa[ch[!d][x]]=y,ch[d][y]=ch[!d][x];
ch[!d][x]=y;
pushup(y),pushup(x);
}
inline void splay(int x) {
for(;!isroot(x);) {
int y=fa[x],z=fa[y];
if (!isroot(y)){
if ((ch[1][y]==x)^(ch[1][z]==y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
int nx[maxn<<1],to[maxn<<1],hd[maxn],cnt;
inline void add(int u,int v) {nx[++cnt]=hd[u],to[cnt]=v,hd[u]=cnt;}
ll dfs(int x,int FA) {
fa[x]=FA;
s[x]=val[x];
ll mx=val[x];
int p=0;
cross(i,x) if (to[i]!=FA) {
dfs(to[i],x);
s[x]+=s[to[i]];
if (s[to[i]]>mx) p=to[i],mx=s[to[i]];
}
if ((mx<<1)>=s[x]+1) {
ans+=(s[x]-mx)<<1;
if (p!=0) lv[x]=s[x]-val[x]-mx,rs=p;
else lv[x]=s[x]-val[x];
}
else ans+=s[x]-1,lv[x]=s[x]-val[x];
}
inline ll calc(int x) {
if (rs) return (s[x]-s[ls]-s[rs])<<1;
else if ((val[x]<<1)>s[x]-s[ls]) return (s[x]-s[ls]-val[x])<<1;
else return s[x]-s[ls]-1;
}
void update(int x,int v) {
splay(x);
ans-=calc(x);
s[x]+=v,val[x]+=v;
if ((s[rs]<<1)<=s[x]-s[ls]) lv[x]+=s[rs],s[x]-=s[rs],rs=0;
pushup(x);
ans+=calc(x);
int y=0;
for(y=x,x=fa[x];x;y=x,x=fa[x]) {
splay(x),ans-=calc(x);
s[x]+=v,lv[x]+=v;
if ((s[rs]<<1)<=s[x]-s[ls]) lv[x]+=s[rs],rs=0;
if ((s[y]<<1)>s[x]-s[ls]) lv[x]-=s[y],rs=y;
pushup(x);
ans+=calc(x);
}
}
int n,m;
int main() {
n=rd(),m=rd();
rep(i,1,n) val[i]=rd();
rep(i,1,n-1) {
int x=rd(),y=rd();
add(x,y),add(y,x);
}
dfs(1,0);
wrt(ans,'\n');
rep(_i,1,m) {
int x=rd(),v=rd();
update(x,v);
wrt(ans,'\n');
}
}
avatar

  1. 1. ZJOI2018历史
    1. 1.1. 先不管修改
    2. 1.2. 有了修改怎么办
    3. 1.3. 一些实现相关
    4. 1.4. 代码