题解：P10930 异象石

· · 题解

不是，哥们，你真来啊。

双倍经验：P3320 [SDOI2015] 寻宝游戏。

三倍经验：CF176E Archaeology。

我们先看 P3320。

结论很好猜，模拟一下走的路径就明白了：

假设下图中，4,5,8 号节点有宝物。

红色路径就是我们来时走过的路径。如果我们算上返回时走的路径，那么我们经过的路径经过且仅经过两次。

此时根据直觉，能知道这条路径与 LCA 有关，于是我们先敲一个板子。

void dfs(int u,int fa,int w){
    dep[u]=dep[fa]+1;
    dis[u]=dis[fa]+w;
    f[u][0]=fa;
    for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i].se,w=G[u][i].fi;
        if(v==fa) continue;
        dfs(v,u,w);
    }
}
int lca(int x,int y){
    if(x==y) return x;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int getdis(int x,int y){
    return dis[x]+dis[y]-2*dis[lca(x,y)];
}

然后进一步分析。我们先假设只有 (4,5) 一对点（单程）：

我们发现，结合 LCA，从 4 到 5 的路径长度可以表示为 dis_4+dis_5-2\times dis_{2}=dis_4+dis_5-2\times dis_{lca_{4,5}}。

对于 (5,8)，(4,8) 两对点，也是如此。

但是我们还发现，如果把宝物点的数量继续增多，那么点对的顺序将不能随意变化。模拟之后，我们发现点对的顺序仅仅和点的 dfs 序有关，且最终 n 个点组成 n 个点对，拆开后变成一个环（因为最终要回到最开始的点）。实际上，原图点的顺序就是 dfs 序。

我们再假设原图中 9 号点也有宝物，那么 4 个点对分别是 (4,5),(5,8),(8,9),(9,4)。路径如下（往返）：

设 dist_{u,v}=dis_u+dis_v-2\times dis_{lca_{u,v}}，a_i 为字典序为第 i 大的宝物点，则 ans=dist_{a_1,a_2}+dist_{a_2,a_3}+\cdots+dist_{a_{n-1},a_n}+dist_{a_n,a_1}。动态维护 ans 即可。

dfs 序的顺序是很好维护的，用 set 维护即可，也可以用 rb_tree_tag。

对于本题，由于我们经过的路径经过且仅经过两次，而本题每条路径只需要算一遍，所以直接将答案 \div 2 即可。

代码如下：

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define int long long
using namespace std;
int n,m,x,y,z,t,dep[100001],dis[100001],dfn[100001],f[100001][21],sum,ans;
char op;
bool vis[100001];
vector<PII>G[100001];
set<PII>st;
void dfs(int u,int fa,int w){
    dep[u]=dep[fa]+1;
    dis[u]=dis[fa]+w;
    dfn[u]=++sum;
    f[u][0]=fa;
    for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i].se,w=G[u][i].fi;
        if(v==fa) continue;
        dfs(v,u,w);
    }
}
int lca(int x,int y){
    if(x==y) return x;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int getdis(int x,int y){
    return dis[x]+dis[y]-2*dis[lca(x,y)];
}
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x>>y>>z;
        G[x].push_back({z,y});
        G[y].push_back({z,x});
    }
    dfs(1,0,0);
    cin>>m;
    while(m--){
        cin>>op;
        if(op=='+'||op=='-'){
            cin>>t;
            vis[t]=!vis[t];
            if(vis[t]) st.insert({dfn[t],t});
            auto it1=st.lower_bound({dfn[t],t}),it2=st.upper_bound({dfn[t],t});
            int a=(it1==st.begin()? (*--st.end()).se:(*--it1).se);
            int b=(it2==st.end()? (*st.begin()).se:(*it2).se);
            swap(a,b);
            if(!vis[t]) st.erase({dfn[t],t});
            int d=getdis(t,a)+getdis(t,b)-getdis(a,b);
            if(vis[t]) ans+=d;
            else ans-=d;
        }
        else cout<<ans/2<<endl;
    }
}