隐藏
「UOJ268」「清华集训2016」数据交互 - 树链剖分维护树形动规 | Bill Yang's Blog
0%

「UOJ268」「清华集训2016」数据交互 - 树链剖分维护树形动规

题目大意

    一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据交互时,数据会经过连接这两个服务器的路径上的所有服务器(包括这两个服务器自身)。每个数据交互请求都有一个非负的重要度,越重要的请求显然需要得到越高的优先处理权。此外,如果在某一个时刻存在一条非常重要(可以看作重要度无穷大)、且数据量巨大的交互请求,则所有被该交互经过的服务器都会优先处理这条交互并阻塞,从而导致其他通过这些服务器的交互出现延迟。

    现在,你作为一个网络系统的管理员,要监控整个系统的运行状态。系统的运行也很简单,在每一个时刻,只有可能出现下列二种事件中的一种:

  • 在某两个服务器之间出现一条新的数据交互请求;
  • 某个数据交互请求结束。

    我们假设这些事件中的交互请求的数据量都足够小。你的任务是在每一个时刻的事件结束后,求出:如果突然出现一条非常重要、且数据量巨大的交互请求,那么因其造成延迟的数据交互请求的重要度之和最大可能是多少?


题目分析

首先对题意进行转化:
给出一棵树,每个点有 $ai,bi$ 两个权值,定义一条链 $(x,y)$ 的权值为链上所有点的 $a_i$ 加上 $b_{LCA(x,y)}$。要求单点(LCA)修改 $a_i$、链上(非LCA)修改 $b_i$(修改都是加一个数或减一个数),动态维护权值最大的链。

套路就不用讲了,自行看这里

现在考虑线段树维护的信息。

  • $sum$:此链上的$a$之和。
  • $lmax$:对应重链上的向下插头。
  • $rmax$:对应重链上的向上插头。
  • $ans$:该区间的答案。

上下插头如图所示:

在叶子结点的时候:

  • $sum=a$
  • $lmax=a+b+$轻儿子最长链
  • $rmax=a+$轻儿子最长链
  • $ans=$轻儿子最长链$+$轻儿子次长链

随意合并一下即可。

答案是全局的,而我们没有将每一条重链的答案传递到上一层,故需要单独开一个堆来记录答案。
同时,为了动态得到轻儿子最长链和次长链,还需要对每个重链开一个堆。

上述的堆需要支持删除任意一个存在的元素,用两个堆分别储存加入的和删除的元素即可。(LZX2019:基本操作啊


代码

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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

typedef long long LL;
#define pii pair<LL,LL>
#define mp make_pair

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=100005;

struct Heap {
priority_queue<LL> add,del;
void insert(LL x) {add.push(x);}
void erase(LL x) {del.push(x);}
LL top() {
while(!del.empty()&&add.top()==del.top())add.pop(),del.pop();
return !add.empty()?add.top():0;
}
pii get() {
LL fir=top(),sec=0;
if(fir==0)return mp(0,0);
erase(fir);
sec=top();
insert(fir);
return mp(fir,sec);
}
} f[maxn],ans;

int n,m,step=0,father[maxn],Depth[maxn],Size[maxn],Son[maxn],Top[maxn],Dfn[maxn],M[maxn];
LL a[maxn];
vector<int> edges[maxn];

struct Segment_Tree {
struct Tree {
int left,right;
int lson,rson;
LL lazy,lmax,rmax,sum,ans;
Tree(int l=0,int r=0):left(l),right(r) {lson=rson=lazy=lmax=rmax=sum=ans=0;}
} tree[maxn<<2];
int size;
#define ls tree[index].lson
#define rs tree[index].rson
void build(int &index,int Left,int Right) {
if(!index)index=++size;
tree[index]=Tree(Left,Right);
if(Left==Right)return;
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
}
void push_up(int index) {
tree[index].sum=tree[ls].sum+tree[rs].sum;
tree[index].lmax=max(tree[ls].lmax+tree[rs].sum,tree[rs].lmax);
tree[index].rmax=max(tree[ls].rmax,tree[ls].sum+tree[rs].rmax);
tree[index].ans=max(max(tree[ls].ans,tree[rs].ans),tree[ls].lmax+tree[rs].rmax);
}
void modify_b(int index,int val) {
tree[index].lazy+=val;
tree[index].lmax+=val;
tree[index].ans+=val;
}
void push_down(int index) {
if(!tree[index].lazy)return;
modify_b(ls,tree[index].lazy);
modify_b(rs,tree[index].lazy);
tree[index].lazy=0;
}
void modify_b(int index,int Left,int Right,int val) {
if(Right<tree[index].left||Left>tree[index].right)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {
modify_b(index,val);
return;
}
push_down(index);
modify_b(ls,Left,Right,val);
modify_b(rs,Left,Right,val);
push_up(index);
}
void modify_a(int index,int pos,pii val) {
if(pos<tree[index].left||pos>tree[index].right)return;
if(tree[index].left==tree[index].right) {
tree[index].sum=a[M[pos]];
tree[index].lmax=tree[index].sum+tree[index].lazy+val.first;
tree[index].rmax=tree[index].sum+val.first;
tree[index].ans=tree[index].sum+tree[index].lazy+val.first+val.second;
return;
}
push_down(index);
modify_a(ls,pos,val);
modify_a(rs,pos,val);
push_up(index);
}
} st;

int root[maxn];
LL last[maxn];

void Dfs1(int Now,int fa,int depth) {
father[Now]=fa;
Depth[Now]=depth;
Size[Now]=1;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs1(Next,Now,depth+1);
Size[Now]+=Size[Next];
if(Size[Son[Now]]<Size[Next])Son[Now]=Next;
}
}

void Dfs2(int Now,int top) {
Top[Now]=top;
Dfn[Now]=++step;
M[step]=Now;
if(Son[Now])Dfs2(Son[Now],top);
else st.build(root[top],Dfn[top],Dfn[Now]),ans.insert(0);
for(int Next:edges[Now]) {
if(Next==Son[Now]||Next==father[Now])continue;
Dfs2(Next,Next);
f[Now].insert(0);
}
}

struct Query {
int x,y,v;
} q[maxn];

void update_ans(int x) {
if(last[x]==st.tree[root[x]].ans)return;
ans.erase(last[x]);
ans.insert(last[x]=st.tree[root[x]].ans);
}

void Modify(Query q,int bj) {
int x=q.x,y=q.y,v=q.v*bj;
for(int t; (t=Top[x])!=Top[y]; x=father[t]) {
if(Depth[Top[x]]<Depth[Top[y]])swap(x,y),t=Top[x];
st.modify_b(root[t],Dfn[t],Dfn[x],v);
update_ans(t);
}
if(Dfn[x]>Dfn[y])swap(x,y);
st.modify_b(root[Top[x]],Dfn[x]+1,Dfn[y],v);
update_ans(Top[x]);
a[x]+=v;
for(int t; father[t=Top[x]]; x=father[t]) {
LL last=st.tree[root[t]].rmax;
st.modify_a(root[t],Dfn[x],f[x].get());
update_ans(t);
LL now=st.tree[root[t]].rmax;
if(now!=last)f[father[t]].erase(last),f[father[t]].insert(now);
}
st.modify_a(root[Top[x]],Dfn[x],f[x].get());
update_ans(Top[x]);
}

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Dfs1(1,0,1);
Dfs2(1,1);
for(int i=1; i<=m; i++) {
char opt=' ';
while(opt!='+'&&opt!='-')opt=getchar();
if(opt=='+') {
q[i].x=Get_Int();
q[i].y=Get_Int();
q[i].v=Get_Int();
Modify(q[i],1);
} else Modify(q[Get_Int()],-1);
printf("%lld\n",ans.top());
}
return 0;
}
姥爷们赏瓶冰阔落吧~