正題

題目鏈接:https://jzoj.net/senior/#contest/show/3017/1

---

題目大意

$n$個點的一棵樹，$m$次操作，修改一個地方的寶藏。

每次操作后求拿完所以寶藏并回到原地的最小距離。

---

解題思路

顯然起點在任何一個有寶藏的地方都是最優(yōu)的，而且順著$dfs$序走是最優(yōu)的。

所以對于每次加入的寶藏，我們用二分+樹狀數(shù)組找出兩邊$dfs$序最近的然后用$LCA$對距離進行計算即可。

時間復(fù)雜度$O(n{\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define lowbit(x) (x&-x) using namespace std; const ll N=2e5+10,T=18; struct node{ll to,next,w; }a[N*2]; ll tot,ls[N],f[N][T]; ll dfn[N],rfn[N],dep[N],dis[N],cnt; ll n,m,ans; bool v[N]; struct Tree_Array{ll t[N];void Change(ll x,ll val){while(x<=2*n){t[x]+=val;x+=lowbit(x);}return;}ll Ask(ll x){ll ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans;}ll Query(ll l,ll r){return Ask(r)-Ask(l-1);}ll Get_Pre(ll x){ll l=1,r=n;if(Ask(x)==0)return 0;while(l<=r){ll mid=(l+r)>>1;if(Query(max(x-mid,1ll),x)>0) r=mid-1;else l=mid+1;}return max(x-l,1ll);}ll Get_Aft(ll x){ll l=1,r=n;if(Ask(n*2)-Ask(x)==0)return 0;while(l<=r){ll mid=(l+r)>>1;if(Query(x,min(x+mid,n*2))>0) r=mid-1;else l=mid+1;}return min(x+l,n*2);} }TA; void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w; } void dfs(ll x,ll fa){dfn[++cnt]=x;rfn[x]=cnt;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa) continue;f[y][0]=x;dep[y]=dep[x]+1;dis[y]=dis[x]+a[i].w;dfs(y,x);}return; } ll pref(ll x){ll z;if(z=TA.Get_Pre(rfn[x])) return dfn[z];return dfn[TA.Get_Pre(rfn[x]+n)]; } ll aftf(ll x){ll z;if(z=TA.Get_Aft(rfn[x]+n)) return dfn[z];return dfn[TA.Get_Aft(rfn[x])]; } ll LCA(ll x,ll y){if(dep[x]>dep[y]) swap(x,y);for(ll i=T-1;i>=0;i--)if(dep[f[y][i]]>=dep[x])y=f[y][i];if(x==y) return y;for(ll i=T-1;i>=0;i--)if(f[y][i]!=f[x][i])x=f[x][i],y=f[y][i];return f[x][0]; } ll get_dis(ll x,ll y) {return dis[x]+dis[y]-2*dis[LCA(x,y)];} int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<n;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);addl(x,y,w);addl(y,x,w);}dep[0]=-1;dfs(1,0);for(ll i=1;i<=n;i++)dfn[i+n]=dfn[i]; for(ll i=1;i<T;i++)for(ll j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];ll w=0;while(m--){ll x;scanf("%lld",&x);if(v[x]){v[x]=0;w--;TA.Change(rfn[x],-1);TA.Change(rfn[x]+n,-1);if(w){ll l=pref(x),r=aftf(x);ans=ans-get_dis(l,x)-get_dis(x,r)+get_dis(l,r); }}else{if(w){ll l=pref(x),r=aftf(x);ans=ans+get_dis(l,x)+get_dis(x,r)-get_dis(l,r); }v[x]=1;w++;TA.Change(rfn[x],1);TA.Change(rfn[x]+n,1);}printf("%lld\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的jzoj4050-寻宝游戏【二分,树状数组,LCA】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。