首先按照dfs序弄个时间戳

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

---

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

用set好题

#include
     
      #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
      
       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])    {        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
        
         s;    inc(i,1,m)    {        rd(x);        if(!vis[x])        {            int num=s.size();            if(!num);//为空             else            {                set
         
          ::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
          
           ::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\n",ans); } re 0;}