BZOJ3991: [SDOI2015]寻宝游戏【LCA+平衡树】

3991: [SDOI2015]寻宝游戏

【题目描述】

传送门

【题解】

每条边一定会被经过两次,那么最后答案就是LCA(a[1],a[2])+LCA(a[2],a[3])+…+LCA(a[n-1],a[n])+LCA(a[n],a[1]),重要的是这个顺序怎么确定,DFS序就可以解决,然后用Set或平衡树维护就可以了。

代码如下

#pragma GCC optimize(2)
#include<set>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int n,m,cnt,Dfn[MAXN],Dep[MAXN],Fa[MAXN][30],vis[MAXN];
long long Ans,Sum[MAXN];
struct xcw{
    int Num,ID;
    bool operator <(const xcw b)const{return Num<b.Num;}
};
set<xcw> Tre;
struct Edge{
    int tot,lnk[MAXN],nxt[MAXN<<1],son[MAXN<<1],W[MAXN<<1];
    void Add(int x,int y,int w){son[++tot]=y;W[tot]=w;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
void DFS(int x,int fa){
    Fa[x][0]=fa,Dep[x]=Dep[fa]+1,Dfn[x]=++cnt;
    for(int j=E.lnk[x];j;j=E.nxt[j]) if(E.son[j]!=fa) Sum[E.son[j]]=Sum[x]+E.W[j],DFS(E.son[j],x);
}
void Init(){
    for(int j=0;(1<<j)<=n;j++)
    for(int i=1;i<=n;i++) Fa[i][j]=-1;
    DFS(1,0);Fa[1][0]=0;
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i<=n;i++) if(Fa[i][j-1]!=-1) Fa[i][j]=Fa[Fa[i][j-1]][j-1];
}
long long LCA(int x,int y){
    if(Dep[x]<Dep[y]) swap(x,y);
    int Del=(Dep[x]-Dep[y]);long long Len=0;
    for(int i=0;(1<<i)<=Del;i++) if((1<<i)&Del) Len+=Sum[x]-Sum[Fa[x][i]],x=Fa[x][i];
    if(x==y) return Len;
    for(int i=log2(n);i>=0;i--) if(Fa[x][i]!=-1&&Fa[y][i]!=-1&&Fa[x][i]!=Fa[y][i]) Len+=Sum[x]-Sum[Fa[x][i]]+Sum[y]-Sum[Fa[y][i]],x=Fa[x][i],y=Fa[y][i];
    return Len+Sum[x]-Sum[Fa[x][0]]+Sum[y]-Sum[Fa[y][0]];
}
int FndF(int x){
    set<xcw>::iterator i=Tre.lower_bound((xcw){Dfn[x],x});
    if(i==Tre.begin()) i=Tre.end();
    return (*(--i)).ID;
}
int FndB(int x){
    set<xcw>::iterator i=Tre.lower_bound((xcw){Dfn[x],x});
    if((++i)==Tre.end()) return (*Tre.begin()).ID;
    return (*i).ID;
}
void print(long long x){
    if(x>9) print(x/10);putchar(x%10+48);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read();m=read();
    for(int i=1,x,y,z;i<n;i++) x=read(),y=read(),z=read(),E.Add(x,y,z),E.Add(y,x,z);
    Init();
    for(int i=1;i<=m;i++){
        int x=read();
        if(!vis[x]){
            vis[x]=1;
            if(Tre.size()==0) Tre.insert((xcw){Dfn[x],x}); else
            if(Tre.size()==1) Ans+=2*LCA((*Tre.begin()).ID,x),Tre.insert((xcw){Dfn[x],x});
            else{
                Tre.insert((xcw){Dfn[x],x});
                int L=FndF(x),R=FndB(x);
                Ans+=LCA(L,x)+LCA(x,R)-LCA(L,R);
            }
        }else{
            vis[x]=0;
            if(Tre.size()==1) Tre.erase((xcw){Dfn[x],x}); else
            if(Tre.size()==2) Tre.erase((xcw){Dfn[x],x}),Ans-=2*LCA((*Tre.begin()).ID,x);
            else{
                int L=FndF(x),R=FndB(x);
                Tre.erase((xcw){Dfn[x],x});
                Ans-=LCA(L,x)+LCA(x,R)-LCA(L,R);
            }
        }
        print(Ans);putchar('\n');
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部