隨便選一個點當做根，跑每個點的深度（為了求LCA）d [ u ] ，和到根節點的距離（為了更新答案） l [ u ]

我們發現，由關鍵點和他們的LCA構成的虛樹（其實就是忽略其他節點），由于還要回到原點，所以相當于是樹的所有邊權的2倍

怎么求？對于每一次標記，將所有的標記了的點按時間戳排序，那么答案就是一、二兩點之間的距離，二、三點之間距離。。。。最后一個點和第一個點之間的距離的總和；

而兩點之間的距離等于 l [ u ] + l [ v ] - 2 * l [ lca ( u , v ) ]

維護這些點時可以用set

#include<cstdio> #include<iostream> #include<set> #include<cmath> #define getchar() *S++ #define ll long long #define R register int const int N=100010,Inf=0x3f3f3f3f; char RR[100000005],*S=RR; using namespace std; inline int g() {R ret=0; register char ch; while(!isdigit(ch=getchar())); do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret; } int n,m,num,cnt; int vr[N<<1],nxt[N<<1],w[N<<1],fir[N],dfn[N],rw[N],d[N],f[N][18]; set<int>s; set<int>::iterator it; ll ans,l[N]; bool vis[N]; inline void add(int u,int v,int ww) {vr[++cnt]=v,w[cnt]=ww,nxt[cnt]=fir[u],fir[u]=cnt;} void dfs(int u) { dfn[u]=++num,rw[num]=u;for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];if(d[v]) continue; d[v]=d[u]+1; l[v]=l[u]+w[i]; f[v][0]=u; R p=u;for(R j=0;f[p][j];++j) f[v][j+1]=f[p][j],p=f[p][j];dfs(v);} } inline int lca(int u,int v) {if(d[u]<d[v]) swap(u,v); R lim=log2(d[u])+1;for(R j=lim;j>=0;--j) if(d[f[u][j]]>=d[v]) u=f[u][j];if(u==v) return u;for(R j=lim;j>=0;--j) if(f[u][j]!=f[v][j]) u=f[u][j],v=f[v][j];return f[u][0]; } inline ll dis(int u,int v) {return l[u]+l[v]-2*l[lca(u,v)];} signed main() {fread(RR,sizeof(RR),1,stdin);n=g(),m=g();for(R i=1,u,v,w;i<n;++i) u=g(),v=g(),w=g(),add(u,v,w),add(v,u,w);d[1]=1;dfs(1); s.insert(-Inf),s.insert(Inf);for(R i=1,x;i<=m;++i) { x=g(); register long long flg; if(vis[x]) s.erase(dfn[x]),flg=-1; else s.insert(dfn[x]),flg=1; vis[x]^=1;it=s.upper_bound(dfn[x]); R r=*it,l=*(--it); if(l>=dfn[x]) l=*(--it);//cout<<l<<" "<<dfn[x]<<" "<<r<<endl;if(l!=-Inf) ans+=flg*dis(rw[l],x); if(r!=Inf) ans+=flg*dis(x,rw[r]);if(l!=-Inf&&r!=Inf) ans-=flg*dis(rw[l],rw[r]); register long long tmp=(s.size()>3)?dis(rw[*++s.begin()],rw[*--(--s.end())]):0;printf("%lld\n",ans+tmp);} }

---

2019.04.18

轉載于:https://www.cnblogs.com/Jackpei/p/10732622.html

總結

以上是生活随笔為你收集整理的BZOJ 3991: [SDOI2015]寻宝游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

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