P3320 [SDOI2015]寻宝游戏 题解
题面
需要动态维护一个点集的极小联通子图边权和。可以发现，将点集 \(\{a_i\}\) 中的点按照 dfs 序从小到大排序之后，\(dist(a_1,a_2)+dist(a_2,a_3)+\ldots+dist(a_{k-1},a_k)+dist(a_k,a_1)\) 恰好等于我们要维护的那个边权和的两倍。所以就开一个 set，在加入和删除的时候加上或删去 pre 和 nxt 的贡献即可。
点击查看代码
const int N=1e5+13;
struct Edge{int v,w,nxt;}e[N<<1];
int n,m,h[N],tot;
ll dis[N];
inline void add_edge(int u,int v,int w){e[++tot]=(Edge){v,w,h[u]};h[u]=tot;}
int fa[N],dep[N],siz[N],son[N],top[N],id[N],dfs_clock;
void dfs1(int u,int f,int deep){
dep[u]=deep,fa[u]=f,siz[u]=1;
int maxson=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==f) continue;
dis[v]=dis[u]+e[i].w;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>maxson) maxson=siz[v],son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf,id[u]=++dfs_clock;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]] t;
std::set::iterator it;
int main(){
//file();
read(n),read(m);
for(int i=1;ix,it=t.find((Node){x});
if((++it)!=t.end()) nxt=it->x;
if(pre) sum-=dist(pre,x);if(nxt) sum-=dist(nxt,x);if(pre&&nxt) sum+=dist(pre,nxt);
t.erase((Node){x});
}
else{//insert
t.insert((Node){x});
it=t.find((Node){x});
int pre=0,nxt=0;
if(it!=t.begin()) pre=(--it)->x,it=t.find((Node){x});
if((++it)!=t.end()) nxt=it->x;
if(pre) sum+=dist(pre,x);if(nxt) sum+=dist(nxt,x);if(pre&&nxt) sum-=dist(pre,nxt);
}
it=t.end();--it;
if(it!=t.begin()){
int u=it->x;it=t.begin();int v=it->x;
println(sum+dist(u,v));
}
else println(sum);
}
return 0;
}