luogu P3320 [SDOI2015]寻宝游戏

寻宝游戏"/>

luogu P3320 [SDOI2015]寻宝游戏

题面传送门
题目要求 k k k个连接关键点的边权之和的二倍。
那么 a n s = d i s t ( a 1 , a 2 ) + d i s t ( a 2 , a 3 ) + . . . + d i s t ( a k − 1 , a k ) ans=dist(a_1,a_2)+dist(a_2,a_3)+...+dist(a_{k-1},a_k) ans=dist(a1​,a2​)+dist(a2​,a3​)+...+dist(ak−1​,ak​)
那么加入或删除一个点时对左右两边拆边建边即可。
维护左右两边可以用平衡树维护，这里写了一个非递归式权值线段树维护。
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
代码实现:

#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k,x,y,z,f[400039],flag[100039],ans1,ans2,tot,top[100039],d[100039],fa[100039],siz[100039],son[100039],dfn[100039],dh,tots[100039];
long long q[100039],ans,pus;
char _s;
struct yyy{int to,w,z;};
struct ljb{int head,h[100039];yyy f[200039];inline void add(int x,int y,int z){f[++head]=(yyy){y,z,h[x]};h[x]=head;}
}s;
inline void get(int x,int z){int l=1,r=n,m,now=1;while(l!=r){m=(l+r)>>1;f[now]+=z;if(x<=m) r=m,now<<=1;else l=m+1,now=now<<1|1;}f[now]+=z;
}
inline int find(int x){int l=1,r=n,m,now=1,ans=0;while(l!=r){m=(l+r)>>1;if(x<=m) r=m,now<<=1;else ans+=f[now<<1],l=m+1,now=now<<1|1;}return ans;
}
inline int query(int x){int l=1,r=n,m,now=1;while(l!=r){m=(l+r)>>1;if(x<=f[now<<1])r=m,now<<=1;else l=m+1,x-=f[now<<1],now=now<<1|1;}return l;
}
inline void dfs1(int x,int last){fa[x]=last;d[x]=d[last]+1;siz[x]=1;dfn[++dh]=x;tots[x]=dh;int cur=s.h[x],pus=-1;yyy tmp;while(cur!=-1){tmp=s.f[cur];if(tmp.to!=last){q[tmp.to]=tmp.w+q[x];dfs1(tmp.to,x);siz[x]+=siz[tmp.to];if(pus<siz[tmp.to]) pus=siz[tmp.to],son[x]=tmp.to;}cur=tmp.z;}
}
inline void dfs2(int x,int last){top[x]=last;if(!son[x]) return;dfs2(son[x],last);int cur=s.h[x];yyy tmp;while(cur!=-1){tmp=s.f[cur];if(tmp.to!=fa[x]&&tmp.to!=son[x]) dfs2(tmp.to,tmp.to);cur=tmp.z;}
}
inline void swap(int &x,int &y){x^=y,y^=x,x^=y;}
inline int lca(int x,int y){while(top[x]!=top[y]){if(d[top[x]]<d[top[y]]) swap(x,y);x=fa[top[x]];}if(d[x]>d[y]) swap(x,y);return x;
}
inline long long dist(int x,int y){return q[x]+q[y]-q[lca(x,y)]*2;}
inline void get1(int x){get(tots[x],1);pus=find(tots[x]);if(tot==1)return;if(tot==2) {ans1=dfn[query(2-pus)];ans+=dist(ans1,x)*2;return;}if(!pus){ans2=dfn[query(2)];ans1=dfn[query(tot)];ans+=dist(x,ans2)+dist(x,ans1)-dist(ans1,ans2);return;}if(pus==tot-1){ans2=dfn[query(tot-1)];ans1=dfn[query(1)];ans+=dist(x,ans2)+dist(x,ans1)-dist(ans1,ans2);return;}ans1=dfn[query(pus)];ans2=dfn[query(pus+2)];ans+=dist(x,ans1)+dist(x,ans2)-dist(ans1,ans2);//printf("%d\n",dist(x,ans2));
}
inline void get2(int x){pus=find(tots[x]);get(tots[x],-1);if(!tot)return;if(tot==1) {ans=0;return;}if(pus==tot||!pus){ans2=dfn[query(tot)];ans1=dfn[query(1)];ans-=dist(x,ans2)+dist(x,ans1)-dist(ans1,ans2);return;}ans1=dfn[query(pus)];ans2=dfn[query(pus+1)];ans-=dist(x,ans1)+dist(x,ans2)-dist(ans1,ans2);
}
int main(){
//	freopen("1.in","r",stdin);register int i;memset(s.h,-1,sizeof(s.h));scanf("%d%d",&n,&m);for(i=1;i<n;i++) scanf("%d%d%d",&x,&y,&z),s.add(x,y,z),s.add(y,x,z);dfs1(1,0);dfs2(1,1);for(i=1;i<=m;i++){scanf("%d",&x);if(!flag[x]) tot++,get1(x);else tot--,get2(x);flag[x]^=1;printf("%lld\n",ans);}
}