假虚树，真乱搞...

Problem

https://www.luogu.org/problemnew/solution/P3320

Solution

https://www.luogu.org/blog/zhouyuheng2003/solution-p3320

显然虚树并没有好写的动态维护方式
于是开个 set 大暴力就行

然后可以先算动态相邻再结算两头
这样子的话就不用管去掉两头的情况了
编程复杂度会低一些。

Code

// Code by ajcxsu
// Problem: tresuregame

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void gn(int &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=1e5+10, M=2e5+10;
int h[N], nexp[M], to[M], p=1;
ll W[M];
inline void ins(int a, int b, ll w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }

int n,m;
const int OP=21;
int dfn[N], dep[N], idx;
int gup[N][OP];
int nd[N];
ll sum[N][OP];
void dfs(int x, int k) {
    dep[x]=k, dfn[x]=++idx;
    nd[idx]=x;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) {
            gup[to[u]][0]=x, sum[to[u]][0]=W[u];
            dfs(to[u], k+1);
        }
}
void ini() {
    dfs(1,1);
    for(int j=1;j<OP;j++)
    for(int i=1;i<=n;i++)
        gup[i][j]=gup[gup[i][j-1]][j-1], sum[i][j]=sum[i][j-1]+sum[gup[i][j-1]][j-1];
}

ll dis(int s, int t) {
    s=nd[s], t=nd[t];
    if(dep[s]<dep[t]) swap(s,t);
    ll ret=0;
    for(int j=OP-1;j>=0;j--)
        if(dep[gup[s][j]]>=dep[t]) ret+=sum[s][j], s=gup[s][j];
    if(s!=t) {
        for(int j=OP-1;j>=0;j--)
            if(gup[s][j]!=gup[t][j]) ret+=sum[s][j]+sum[t][j], s=gup[s][j], t=gup[t][j];
        ret+=sum[s][0]+sum[t][0];
    }
    return ret;
}

set<int> nset;
bool li[N];

int main() {
    gn(n), gn(m);
    int u,v,w;
    for(int i=0;i<n-1;i++) gn(u), gn(v), gn(w), ins(u,v,w), ins(v,u,w);
    ini();
    nset.insert(0), nset.insert(n+1);
    int na;
    ll ans=0;
    while(m--) {
        gn(na);
        ll d=-1,ext;
        if(!li[na]) d=1, nset.insert(dfn[na]), li[na]=1;
        else if(li[na]) li[na]=0;
        int bef=*(--nset.find(dfn[na])), aft=*(++nset.find(dfn[na]));
        if(bef>=1) ans+=d*dis(bef, dfn[na]);
        if(aft<=n) ans+=d*dis(dfn[na], aft);
        if(bef>=1 && aft<=n) ans-=d*dis(bef, aft);
        if(!li[na]) nset.erase(dfn[na]);
        bef=*++nset.find(0);
        aft=*--nset.find(n+1);
        if(bef<aft) ext=dis(bef, aft);
        else ext=0;
        printf("%lld\n", ans+ext);
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3320.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆