[SDOI2015] 寻宝游戏

题目大意

给你一棵树，边有边权，现在每个村庄可能会突然有宝藏，又可能会突然没宝藏。

若可以随意选择起点，问每次修改后从起点遍历完所有宝藏再回到起点的最短路径长度。

难度：七星（满分十星）

题解

注：\(dis(x,y)\) 为 \(x\) 到 \(y\) 的距离。

若目前有的点按照 \(dfs\) 序排序后为 \(a\)，则最短路径长度为 \(\sum\limits_{i=1}^{n-1}dis(a_i,a_{i+1})\)。证明不再赘述。

在插入和删除点时，设 \(x\) 的前驱为 \(y\)，后继为 \(z\)，则插入 \(x\) 时答案应加上 \(dis(x,y)+dis(x,z)-dis(y,z)\)，删除时则应当减它。

那么我们现在实际上只需要快速求出前驱后继，可以使用 \(set/\) 权值线段树，这里使用平衡树（替罪羊树，也可以用其他的平衡树代替）。

时间复杂度 \(O(q\log q+n)\)

代码

#include<bits/stdc++.h>
#define ls(x) sgt[x].ls
#define rs(x) sgt[x].rs
#define val(x) sgt[x].val
#define tot(x) sgt[x].tot
#define sz(x) sgt[x].sz
#define dl(x) sgt[x].dl
#define ll long long
using namespace std;
const int N=100005;
const double alpha=0.75;
struct sad_goat{
	int ls,rs,val,tot,sz,dl;
}sgt[N];int q,bk[N],cnt,st[N],tp;
struct sad_goat_tree{
	int rt=0;void dfs(int u){
		if(!u) return;dfs(ls(u));
		if(dl(u)) bk[++cnt]=u;
		else st[++tp]=u;dfs(rs(u));
	}void build(int l,int r,int &u){
		int mid=(l+r)/2;u=bk[mid];
		if(l==r){sgt[u]={0,0,val(u),1,1,1};return;}
		if(l<mid) build(l,mid-1,ls(u));
		if(l==mid) ls(u)=0;
		build(mid+1,r,rs(u));
		sz(u)=sz(ls(u))+sz(rs(u))+1;
		tot(u)=tot(ls(u))+tot(rs(u))+1;
	}void rebuild(int &u){
		cnt=0;dfs(u);if(cnt)
			build(1,cnt,u);else u=0;
	}int check(int u){
		double b=1.0*max(sz(ls(u)),sz(rs(u)));
		double a=1.0*sz(u)*alpha;return (a<=b);
	}void add(int &u,int x){
		if(!u){
			u=st[tp--];
			sgt[u]={0,0,x,1,1,1};
			return;
		}sz(u)++;tot(u)++;
		if(val(u)>=x) add(ls(u),x);
		else add(rs(u),x);
		if(check(u)) rebuild(u);
	}int rank(int u,int x){
		if(u==0) return 0;if(x<=val(u)) return rank(ls(u),x);
		return sz(ls(u))+dl(u)+rank(rs(u),x);
	}void delk(int &u,int k){
		sz(u)--;if(dl(u)&&sz(ls(u))+1==k){
			dl(u)=0;return;}
		if(sz(ls(u))+dl(u)>=k) delk(ls(u),k);
		else delk(rs(u),k-sz(ls(u))-dl(u));
	}void del(int x){
		delk(rt,rank(rt,x)+1);
		if(tot(rt)*alpha>=sz(rt))
			rebuild(rt);
	}int kth(int k){
		int u=rt;while(u){
			if(dl(u)&&sz(ls(u))+1==k) return val(u);
			else if(sz(ls(u))>=k) u=ls(u);
			else k-=sz(ls(u))+dl(u),u=rs(u);
		}return val(u);
	}
}t;struct edge{int nxt,to;ll w;}e[N*2];
int n,m,k,d,df[N],dep[N],fa[N][20];
int v[N],dn[N],h[N];ll ans,dt[N];
void add(int x,int y,int z){
	e[++k].to=y;e[k].w=z;
	e[k].nxt=h[x];h[x]=k;
}void dfs(int x,int f){
	df[x]=++d;fa[x][0]=f;dn[d]=x;
	for(int i=0;i<19;i++)
		fa[x][i+1]=fa[fa[x][i]][i];
	for(int i=h[x],y;i;i=e[i].nxt)
		if((y=e[i].to)!=f){
			dt[y]=dt[x]+e[i].w;
			dep[y]=dep[x]+1;dfs(y,x);
		}
}int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;~i;i--)
		if(dep[x]-dep[y]>=(1<<i))
			x=fa[x][i];
	if(x==y) return x;
	for(int i=19;~i;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}ll dis(int x,int y){
    return dt[x]+dt[y]-2*dt[lca(x,y)];
}int main(){
	for(int i=N-1;i;i--) st[++tp]=i;
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);cin>>n>>m;
	for(int i=1,x,y,z;i<n;i++)
		cin>>x>>y>>z,add(x,y,z),add(y,x,z);
	dfs(1,0);while(m--){
		int x;cin>>x;x=df[x];
		if(!v[x]) t.add(t.rt,x);
		int y=t.kth(t.rank(t.rt,x));
        int z=t.kth(t.rank(t.rt,x+1)+1);
		if(!y) y=t.kth(sz(t.rt));if(!z) z=t.kth(1);
		if(v[x]) t.del(x);x=dn[x];y=dn[y];z=dn[z];
		ll d=dis(x,y)+dis(x,z)-dis(y,z);
		if(v[df[x]]) ans-=d,v[df[x]]=0; 
		else ans+=d,v[df[x]]=1;
		cout<<ans<<"\n";
	}return 0;
}