题意:求在树中从任意点开始,经过若干个关键点回到原点的最小距离

要求支持在线将某个点设置(取消)为关键点,以及询问答案

n,m<=100000 len[i]<=10^9

思路:显然是一个虚树的模型,但并不需要虚树

其实就是求虚树的所有路径长度之和的2倍

思考后可以发现,必定是按DFS序从小到大走,再从最大点回到最小点总路程最短

所以只需要维护DFS序的插入,删除,前驱,后继,最大,最小,splay即可

插入点i时找到与它DFS序相邻的点x和y,对答案有dis(x,i)+dis(y,i)-dis(x,y)的贡献

最后加上首尾长度

 var t:array[..,..]of longint;
f:array[..,..]of longint;
fa,rev,size:array[..]of longint;
flag,dfn,id,dep,head,vet,next,len,b:array[..]of longint;
dis,num:array[..]of int64;
n,m,i,x,y,tot,root,cnt,time,z:longint;
ans,v,tmp,oo,l,r:int64; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; procedure pushup(x:longint);
var l,r:longint;
begin
l:=t[x,]; r:=t[x,];
size[x]:=size[l]+size[r]+;
end; procedure rotate(x:longint;var k:longint);
var y,z,l,r:longint;
begin
y:=fa[x]; z:=fa[y];
if t[y,]=x then l:=
else l:=;
r:=l xor ;
if y<>k then
begin
if t[z,]=y then t[z,]:=x
else t[z,]:=x;
end
else k:=x;
fa[x]:=z; fa[y]:=x; fa[t[x,r]]:=y;
t[y,l]:=t[x,r]; t[x,r]:=y;
pushup(y);
pushup(x);
end; procedure splay(x:longint;var k:longint);
var y,z:longint;
begin
while x<>k do
begin
y:=fa[x]; z:=fa[y];
if y<>k then
begin
if (t[y,]=x)xor(t[z,]=y) then rotate(x,k)
else rotate(y,k);
end
else k:=x;
rotate(x,k);
end;
end; function kth(x:longint):longint;
var k,tmp:longint;
begin
k:=root;
while k<> do
begin
tmp:=size[t[k,]]+;
if tmp=x then exit(k)
else if tmp>x then k:=t[k,]
else
begin
k:=t[k,]; x:=x-tmp;
end;
end;
end; function pred(x:int64):int64;
var k:longint;
last:int64;
begin
k:=root; last:=-oo;
while k<> do
begin
if num[k]<x then begin last:=num[k]; k:=t[k,]; end
else k:=t[k,];
end;
exit(last);
end; function succ(x:int64):int64;
var k:longint;
last:int64;
begin
k:=root; last:=oo;
while k<> do
begin
if num[k]>x then begin last:=num[k]; k:=t[k,]; end
else k:=t[k,];
end;
exit(last);
end; function rank(x:int64):longint;
var k:longint;
begin
rank:=; k:=root;
while k<> do
begin
if num[k]<x then begin rank:=rank+size[t[k,]]+; k:=t[k,]; end
else k:=t[k,];
end;
end; procedure ins(x:int64);
var k,k1,k2:longint;
begin
k:=rank(x);
k1:=kth(k-);
k2:=kth(k);
splay(k1,root);
splay(k2,t[root,]);
k:=t[root,];
inc(cnt); t[k,]:=cnt; fa[cnt]:=k; size[cnt]:=; num[cnt]:=x;
inc(tot);
end; procedure del(x:int64);
var k,k1,k2:longint;
begin
k:=rank(x);
k1:=kth(k-);
k2:=kth(k+);
splay(k1,root);
splay(k2,t[root,]);
k1:=t[root,]; k2:=t[k1,];
t[k1,]:=; size[k1]:=size[t[k1,]]+;
fa[k2]:=; t[k2,]:=; t[k2,]:=; size[k2]:=; num[k2]:=;
dec(tot);
end; function lca(x,y:longint):longint;
var i,d:longint;
begin
if dep[x]<dep[y] then swap(x,y);
d:=dep[x]-dep[y];
for i:= to do
if d and (<<i)> then x:=f[x,i];
for i:= downto do
if f[x,i]<>f[y,i] then
begin
x:=f[x,i]; y:=f[y,i];
end;
if x=y then exit(x);
exit(f[x,]);
end; function query(x,y:longint):int64;
var q:longint;
begin
q:=lca(x,y);
exit(dis[x]+dis[y]-*dis[q]);
end; procedure add(a,b,c:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
len[tot]:=c;
head[a]:=tot;
end; procedure dfs(u:longint);
var i,e,v:longint;
begin
flag[u]:=;
inc(time); dfn[u]:=time; id[time]:=u;
for i:= to do
begin
if dep[u]<<<i then break;
f[u,i]:=f[f[u,i-],i-];
end;
e:=head[u];
while e<> do
begin
v:=vet[e];
if flag[v]= then
begin
dep[v]:=dep[u]+;
dis[v]:=dis[u]+len[e];
f[v,]:=u;
dfs(v);
end;
e:=next[e];
end;
end; begin
assign(input,'bzoj3991.in'); reset(input);
assign(output,'bzoj3991.out'); rewrite(output);
readln(n,m);
for i:= to n- do
begin
readln(x,y,z);
add(x,y,z);
add(y,x,z);
end;
dfs();
oo:=<<;
num[]:=oo; t[,]:=; size[]:=;
num[]:=-oo; fa[]:=; size[]:=;
root:=; cnt:=; tot:=;
for i:= to m do
begin
readln(x);
if b[x]= then begin v:=; ins(dfn[x]); end
else begin v:=-; del(dfn[x]); end;
b[x]:=b[x] xor ;
l:=pred(dfn[x]);
r:=succ(dfn[x]);
if l<>-oo then ans:=ans+v*query(id[l],x);
if r<>oo then ans:=ans+v*query(id[r],x);
if (l<>-oo)and(r<>oo) then ans:=ans-v*query(id[l],id[r]);
tmp:=;
if tot> then
begin
l:=kth();
r:=kth(tot-);
tmp:=query(id[num[l]],id[num[r]]);
end;
writeln(ans+tmp);
end;
close(input);
close(output);
end.
05-22 11:43
查看更多