Fork me on GitHub

Uoj#374.【ZJOI2018】历史

Uoj#374.【ZJOI2018】历史 题解

题意:

  • 给出以$1$为根的一棵树的$n$个节点的$\rm access$次数,求最大可能的轻重链切换次数。
  • 带$m$次单点增加次数并询问。
  • $1\le n,m\le 4\times 10^5$。

吐槽:

  • 作为考场上想$O(n\times m)$暴力想了一年的选手,怕是没有希望了。
  • 听闻小猫相出了一种$O(n\log^3n)$的做法,然后出考场发现是$O(n\log n)$的。
  • 听小猫说他把$\rm lct$的$\rm log$乘了上去,并且认为$\log (a\times b)=\log (a)\times \log(b)$。
  • 我也只能2333了。
  • 不过似乎因为没有加读入优化变成了$80$分,似乎挺悲伤的。

题解:

  • 首先考虑一种暴力,每次计算一个节点产生的贡献(我们规定一条相同颜色的链的贡献由最底部的点产生)。
  • 显然每个点的贡献只跟其子树内部(包含本身)的相对顺序有关。
  • 如果$max(max_{y\in son_x}size_y,a_x)\le\lfloor\frac{size_x+1}{2}\rfloor$,那么答案为$size_x-1$。
  • 否则答案为$2\times (size_x-max(max_{y\in son_x}size_y,a_x))$。
  • 对于每个$size_x>size_{fa_x}$的节点$x$,我们将它向$fa_x$连一条重边,否则连一条轻边。
  • 那么每走一次轻边,$size$至少乘以$2$,所以每次经过的轻边复杂度为$O(\log (\sum a_i))$。
  • 我们发现一次单点增加次数可以类比一种特殊的$\rm access$的操作。
  • 对于加的点$x$,如果它不存在重儿子,就正常修改单点的答案。
  • 否则判断其重边是否依旧成立,按照需要继续连接或断开并更改答案。
  • 然后像普通$\rm access$一样,但是每次轻重链切换前先判断是否可以切换,再暴力修改轻边的答案。
  • 注意到重链上的点的$max(max_{y\in son_x}size_y,a_x)$和$size_x$变化幅度相同,也就是答案不会改变。
  • 所以每次只需要暴力修改轻边答案以及$x$的重儿子即可。
  • 复杂度分析类比$splay$即可得知。
  • 复杂度$O(n+q\log(\sum a_i))$。
  • (千万别分析错复杂度或者忘写读入优化)

代码:

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
#include <bits/stdc++.h>
#define gc getchar()
#define N 400009
using namespace std;
typedef long long ll;
int n,m,first[N],number,chk[N];
ll dp[N],Ans,a[N];
struct edge
{
int to,next;
void add(int x,int y)
{
to=y,next=first[x],first[x]=number;
}
}e[N<<1];
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
ll get(ll x,ll y)
{
return min(2ll*(x-y),x-1);
}
struct LCT
{
int ch[N][2],fa[N],rev[N];
ll size[N],sum[N];
bool is_root(int x)
{
return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
void up(int x)
{
size[x]=a[x]+sum[x];
if (ch[x][0]) size[x]+=size[ch[x][0]];
if (ch[x][1]) size[x]+=size[ch[x][1]];
}
void rotate(int x)
{
int y=fa[x],z=fa[y],l=ch[y][1]==x;
if (!is_root(y)) ch[z][ch[z][1]==y]=x;
fa[x]=z,fa[y]=x,fa[ch[x][!l]]=y;
ch[y][l]=ch[x][!l],ch[x][!l]=y;
up(y),up(x);
}
void splay(int x,int y=0)
{
for (;!is_root(x);rotate(x))
if (!is_root(y=fa[x])) rotate(ch[fa[y]][0]==y^ch[y][0]==x?x:y);
}
void ins(int x,ll y)
{
for (int t=0;x;t=x,x=fa[x])
{
splay(x);
ll now=size[t];
ll nxt=size[x];
if (ch[x][0]) nxt-=size[ch[x][0]];
nxt+=y;
if (!t)
{
a[x]+=y;
if (ch[x][1]&&size[ch[x][1]]<=(nxt+1)/2)
{
Ans-=get(nxt-y,size[ch[x][1]]);
Ans+=get(nxt,a[x]);
sum[x]+=size[ch[x][1]];
ch[x][1]=0;
}
else
if (!chk[x])
{
if (ch[x][1]) Ans+=get(nxt,size[ch[x][1]])-get(nxt-y,size[ch[x][1]]);
else
{
Ans-=get(nxt-y,a[x]-y);
Ans+=get(nxt,a[x]);
}
}
}
else
{
sum[x]+=y;
if (ch[x][1]&&size[ch[x][1]]<=(nxt+1)/2)
{
Ans-=get(nxt-y,size[ch[x][1]]);
Ans+=get(nxt,a[x]);
sum[x]+=size[ch[x][1]];
ch[x][1]=0;
}
else
if (!chk[x])
{
if (ch[x][1]) Ans+=2*y;
else
{
Ans-=get(nxt-y,a[x]);
Ans+=get(nxt,a[x]);
}
}
if (now>(nxt+1)/2)
{
Ans-=get(nxt,a[x]);
Ans+=get(nxt,now);
sum[x]+=size[ch[x][1]];
ch[x][1]=t;
sum[x]-=size[ch[x][1]];
}
}
up(x);
}
}
void tree_dp(int x)
{
size[x]=a[x];
dp[x]=0;
ll Max=a[x];
for (int i=first[x];i;i=e[i].next)
if (e[i].to!=fa[x])
{
fa[e[i].to]=x;
tree_dp(e[i].to);
dp[x]+=dp[e[i].to];
Max=max(Max,size[e[i].to]);
size[x]+=size[e[i].to];
}
if (Max>(size[x]+1)/2) dp[x]+=2ll*(size[x]-Max);
else dp[x]+=size[x]-1;
for (int i=first[x];i;i=e[i].next)
if (e[i].to!=fa[x])
{
if (size[e[i].to]>(size[x]+1)/2) ch[x][1]=e[i].to;
else sum[x]+=size[e[i].to];
}
}
}lct;
int main()
{
n=read(),m=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<n;i++)
{
int x=read(),y=read();
e[++number].add(x,y),e[++number].add(y,x);
chk[x]++,chk[y]++;
}
for (int i=2;i<=n;i++)
if (chk[i]>1) chk[i]=0;
chk[1]=0;
lct.tree_dp(1);
Ans=dp[1];
printf("%lld\n",Ans);
while (m--)
{
int x=read(),y=read();
lct.ins(x,y);
printf("%lld\n",Ans);
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#374.【ZJOI2018】历史

文章作者:wzf2000

发布时间:2018年03月25日 - 13:03

最后更新:2018年03月25日 - 14:03

原始链接:https://wzf2000.github.io/2018/03/25/Uoj374/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。