P3320 [SDOI2015]寻宝游戏（LCA）

题目

首先按照dfs序弄个时间戳

将要访问的点按照时间戳顺序,两两求距离即为答案

---

反正就是用数据结构维护这个顺序

用set好题

#include<bits/stdc++.h>
#define re return
#define ll long long
#define dec(i,l,r) for(int i=l;i>=r;--i)
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
}

const int maxn=1e5+5;

int n,m,k,tot,hd[maxn],cnt[maxn],vis[maxn];
int rev[maxn],fa[maxn][25],deep[maxn];
ll ans,dis[maxn][25];
struct node{
    int to,nt,val;
}e[maxn<<1];
inline void add(int x,int y,int z)
{
    e[++k].to=y;e[k].val=z;e[k].nt=hd[x];hd[x]=k;
    e[++k].to=x;e[k].val=z;e[k].nt=hd[y];hd[y]=k;
}

inline void dfs(int x,int pre)
{
    deep[x]=deep[pre]+1; 
    cnt[x]=++tot;
    rev[tot]=x;
    for(int i=0;fa[fa[x][i]][i];++i)
    {
        fa[x][i+1]=fa[fa[x][i]][i];
        dis[x][i+1]=dis[x][i]+dis[fa[x][i]][i];
    }    
    
    for(int i=hd[x];i;i=e[i].nt)
    {
        int v=e[i].to;
        if(v==pre)continue;
        fa[v][0]=x;
        dis[v][0]=e[i].val;
        dfs(v,x);
    }
}

inline ll LCA(int x,int y)
{
    ll ANS=0;
    if(deep[x]<deep[y])swap(x,y);
    
    dec(i,20,0)
    if(deep[fa[x][i]]>=deep[y])
    {
        ANS+=dis[x][i];
        x=fa[x][i];
    }    
    
    if(x==y)re ANS;
    dec(i,20,0)
    if(fa[x][i]!=fa[y][i])
    {
        ANS+=dis[x][i]+dis[y][i];
        x=fa[x][i];
        y=fa[y][i];
    }
    ANS+=dis[x][0]+dis[y][0];
    re ANS;
}

int main()
{
    
    //freopen("in.txt","r",stdin);
    int x,y,z;
    rd(n);
    rd(m);
    inc(i,2,n)
    {
        rd(x),rd(y),rd(z);
        add(x,y,z); 
    }
    
    dfs(1,0);
    
    set<int>s;

    inc(i,1,m)
    {
        rd(x);
        if(!vis[x])
        {
            int num=s.size();
            if(!num);//为空 
            else
            {
                set<int>::iterator it=s.lower_bound(cnt[x]);
                int l,r;
                if(it!=s.begin())
                {
                    l=*(--it);
                    ++it;
                }    
                else l=*(s.rbegin());
            
                if(it!=s.end())
                    r=*it;
                else r=*s.begin();
                
                ans-=LCA(rev[l],rev[r]);
                ans+=LCA(rev[l],x);
                ans+=LCA(rev[r],x);
            }

            s.insert(cnt[x]);
            
        }
        else 
        {
            int num=s.size();
            set<int>::iterator it=s.lower_bound(cnt[x]);
            if(num==1);
            else 
            {
                int l,r;
                
                if(it!=s.begin())
                {
                    l=*--it;
                    ++it;
                }
                else l=*(s.rbegin());
                
                ++it;
                if(it!=s.end())
                    r=*it;
                else r=*s.begin();
                --it;
                
                ans+=LCA(rev[l],rev[r]);
                ans-=LCA(rev[l],x);
                ans-=LCA(rev[r],x);
            }
            
            s.erase(it);
        }
        vis[x]^=1;

            printf("%lld
",ans);
    
    }
    re 0;
}