[SDOI2015]寻宝游戏

Description

Soluiton

结论1：\(x_1, x_2, x_3, x_4, \cdots x_k\) 到根的路径的并的和等于把 \(x_1, x_2\cdots x_k\) 按 \(dfn\) 排序后所有点到根的 \(dis\) 减去相邻两个点 LCA 到根的 \(dis\)。

证明：考虑用增量法，已知有两点 \(x_1, x_3\) ，\(x_2\) 插入在 \(x_1, x_3\) 之间（dfn序位于 \(x_1\) ，\(x_3\) 之间），那么 \(x_2\) 在 \(LCA(x_1, x_3)\) 的子树内，假设 \(LCA(x_3, x_1) = LCA(x_2, x_3)\) 此时原来的 \(dis(x_1) + dis(x_3) - dis(LCA(x_1,x_3))\) 就要变成 \(dis(x_1) + dis(x_3) - dis(LCA(x_1, x_3)) + dis(x_2) - dis(LCA(x_1, x_2)) = dis(x_1) + dis(x_2) + dis(x_3) - dis(LCA(x_1, x_2)) - dis(LCA(x_2, x_3))\)。

当 \(x\) 插入开头和结尾的时候类似可证。

结论2：\(x_1, x_2,\cdots ,x_k\) 的 LCA 为他们按 dfn 排序后开头和结尾两点的 LCA。

证明：由 dfn 序的性质，中间的点 \(x_2,\cdots x_{k-1}\) 都在 \(LCA(x_1, x_k)\) 的子树内。

回到本题

不难发现就是要我们求若干个点 \(x_1, \cdots ,x_k\) 到 \(LCA(x_1, \cdots, x_k)\) 路径的并。

有上面那两个结论就很好做了，把这 \(k\) 个点按 dfn 序排序。

那么答案为：

\[\begin{aligned}&2\left(\left(\sum_{i=1}^k dis(x_i)\right) -\left(\sum_{i=1}^{k-1}dis(LCA(x_i,x_{i+1}))\right) - dis(LCA(x_1,x_k))\right)\\=&2\left(\frac{1}{2}\sum_{i=1}^{k-1}dis(x_i)+dis(x_{i+1})-2dis(LCA(x_i,x_{i+1}))\right) + dis(x_1) + dis(x_k) - 2dis(LCA(x_1, x_k))\\=&\sum_{i=1}^{k-1}dis(x_i,x_{i+1})+dis(x_1,x_k)\end{aligned}\]

于是用set维护dfn序删除和加点就查前驱后继。

code

#include <iostream>
#include <set>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <fstream>

using namespace std;

#define LL long long
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define MP(x, y) std::make_pair(x, y)
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define REP(i, a, b) for (register int (i) = (a); (i) <= (b); ++(i))
#define GO cerr << "GO" << endl;

inline void proc_status()
{
    ifstream t("/proc/self/status");
    cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}
template<class T> inline T read()
{
    register char c;
    register T x(0), f(1);
    while (!isdigit(c = getchar())) if (c == '-') f = -1;
    while (x = (x << 1) + (x << 3) + (c xor 48), isdigit(c = getchar()));
    return x * f;
}
template<typename T> inline bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }

const int maxN=1e5;

int n,m;
int ver[maxN*2],nxt[maxN*2],edge[maxN*2],head[maxN+1],tot;
int dfn[maxN+2],f[maxN+2][19],dep[maxN+2],dfst,rev[maxN+2];
bool vis[maxN+2];
LL dis[maxN+2];
set<int> s;

void link(int u,int v,int w)
{
    ver[++tot]=v,nxt[tot]=head[u],edge[tot]=w,head[u]=tot;
}

void DFS(int u,int fa)
{
    dfn[u]=++dfst;
    rev[dfst]=u;
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<18;++i)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i;i=nxt[i])
    {
        int v=ver[i];
        if (v==fa)continue;
        dis[v]=dis[u]+edge[i];
        DFS(v,u);
    }
}

int GetLca(int u, int v)
{
    if(dep[u]<dep[v])
        swap(u,v);
    for(int i=17;i>=0;--i)
        if(dep[f[u][i]]>=dep[v])
            u=f[u][i];
    assert(dep[u]==dep[v]);
    if(u==v)return u;
    for(int i=17;i>=0;--i)
        if(f[u][i]!=f[v][i])
            u=f[u][i],v=f[v][i];
    assert(f[u][0]==f[v][0]);
    return f[u][0];
}

LL GetDis(int u, int v)
{
    int Lca=GetLca(u,v);
    return dis[u]+dis[v]-dis[Lca]*2;
}

#define Iter set<int>::iterator

LL ans(0);
Iter it;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("xhc.in", "r", stdin);
    freopen("xhc.out", "w", stdout);
#endif
    n=read<int>(),m=read<int>();
    for(int i=1;i<n;++i)
    {
        int u=read<int>(),v=read<int>(),w=read<int>();
        link(u,v,w),link(v,u,w);
    }
    DFS(1,0);
    for(int i=1;i<=m;++i)
    {
        int x=read<int>();
        if(!vis[x])
        {
            vis[x]=1;
            if(s.size()==0)
            {
                s.insert(dfn[x]);
                printf("%lld\n",ans);
                continue;
            }
            Iter n=s.lower_bound(dfn[x]);
            if(n==s.end())
            {
                Iter p=n;p--;
                ans+=GetDis(x,rev[*p])+GetDis(x,rev[*s.begin()])-GetDis(rev[*s.begin()],rev[*p]);
                s.insert(dfn[x]);
            }else if(n==s.begin())
            {
                ans+=GetDis(x,rev[*n])+GetDis(x,rev[*s.rbegin()])-GetDis(rev[*n],rev[*s.rbegin()]);
                s.insert(dfn[x]);
            }else
            {
                Iter p=n;p--;
                ans+=GetDis(x,rev[*p])+GetDis(x,rev[*n])-GetDis(rev[*p],rev[*n]);
                s.insert(dfn[x]);
            }
        }
        else
        {
            vis[x]=0;
            if(s.size()==1)
            {
                s.erase(dfn[x]);
                ans=0;
                printf("%lld\n",ans);
                continue;
            }
            Iter cur=s.find(dfn[x]);
            Iter n=cur;n++;
            if(n==s.end())
            {
                Iter p=cur;p--;
                ans-=GetDis(x,rev[*p])+GetDis(x,rev[*s.begin()])-GetDis(rev[*s.begin()],rev[*p]);
                s.erase(dfn[x]);
            }else if(cur==s.begin())
            {
                ans-=GetDis(x,rev[*n])+GetDis(x,rev[*s.rbegin()])-GetDis(rev[*n],rev[*s.rbegin()]);
                s.erase(dfn[x]);
            }else
            {
                Iter p=cur;p--;
                ans-=GetDis(x,rev[*p])+GetDis(x,rev[*n])-GetDis(rev[*p],rev[*n]);
                s.erase(dfn[x]);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}