解析

大結論題…
實在是不知道這題和虛樹有半毛錢關系嗎…

引理
給出一個按照dfs排列的點集S={a1,a2…ak}
它們的極小聯通子樹的邊權和的二倍等于$\sum dis(a_1,a_2)+dis(a_2,a_3)+...+dis(a_k?1,a_k)+dis(a_k,a_1)$

證明

按照本題的情景說吧，似乎更好理解一些
最優的路徑是一個環，所以其實從哪個點開始都是可以的
所以我們其實就是決定一個先去哪里的問題
…不難發現按照dfs序走肯定是不劣的（或者說，就是最優的）
這什么垃圾證明

然后…本題就做完了…
寫個lca板子，再維護個set指針找找前驅后繼加加特判即可

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=1e5+100; const int mod=998244353; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m;struct node{int to,nxt;ll w; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y,int w){p[++cnt]=(node){y,fi[x],w};fi[x]=cnt;return; }int pl[N][18]; ll dep[N]; int siz[N],pos[N],tim; void init(int x,int f){siz[x]=1;pos[x]=++tim;pl[x][0]=f;for(int k=1;pl[x][k-1];k++) pl[x][k]=pl[pl[x][k-1]][k-1];for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dep[to]=dep[x]+p[i].w;init(to,x);siz[x]+=siz[to];}return; } inline int Lca(int x,int y){if(pos[x]<=pos[y]&&pos[y]<=pos[x]+siz[x]-1) return x;for(int k=17;k>=0;k--){int o=pl[x][k];if(!o||(pos[o]<=pos[y]&&pos[y]<=pos[o]+siz[o]-1)) continue;x=o;}return pl[x][0]; } inline ll dis(int x,int y){int lca=Lca(x,y);return dep[x]+dep[y]-2*dep[lca]; }struct id{int x; }; bool operator < (const id a,const id b){return pos[a.x]<pos[b.x]; } bool operator > (const id a,const id b){return b<a; } set<id>s; set<id>::iterator it1,it2; int num; ll ans(0);int main() { #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();m=read();for(int i=1;i<n;i++){int x=read(),y=read(),w=read();addline(x,y,w);addline(y,x,w);}init(1,0);for(int t=1;t<=m;t++){int x=read();id o=(id){x};if(s.count(o)){s.erase(o),num--;if(num==0){printf("0\n");continue;}id fir=*s.begin();if(fir>o){it1=s.end();it1--;it2=s.begin();}else if(s.upper_bound(o)==s.end()){it1=s.end();it1--;it2=s.begin();}else{it1=it2=s.upper_bound(o);it1--;}int pre=(*it1).x,suf=(*it2).x;ans-=dis(pre,x)+dis(suf,x)-dis(pre,suf);}else{if(num==0){s.insert(o);num++;printf("0\n");continue;}id fir=(*s.begin());//printf("ok x=%d\n",fir.x);if(fir>o){it1=s.end();it1--;it2=s.begin();}else if(s.upper_bound(o)==s.end()){it1=s.end();it1--;it2=s.begin();}else{it1=it2=s.upper_bound(o);it1--;}int pre=(*it1).x,suf=(*it2).x;ans+=dis(pre,x)+dis(suf,x)-dis(pre,suf);//printf("pre=%d suf=%d\n",pre,suf);s.insert(o);num++;}printf("%lld\n",ans);}return 0; } /* */

總結

以上是生活随笔為你收集整理的P3320：寻宝游戏（生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。