蒟蒻刚学虚树求助QAQ--wa了4个点
查看原帖
蒟蒻刚学虚树求助QAQ--wa了4个点
247695
AuroraKelsey楼主2020/8/26 11:08
#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100005; 
const int M=200005;
typedef long long LL; 
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

int n,m;
int hd[N],nxt[M],to[M],w[M],tot;
inline void add(int x,int y,int z) {
    to[++tot]=y;w[tot]=z;nxt[tot]=hd[x];hd[x]=tot;
}

LL dep[N],dis[N];//
int f[N][20],dfn[N],rev[N],dfn_cnt;
void dfs(int x,int fa,LL d) {
    dep[x]=d;
    f[x][0]=fa;
    dfn[x]=++dfn_cnt;rev[dfn_cnt]=x;
    for(int i=1;i<=18&&f[x][i-1];i++)
        f[x][i]=f[f[x][i-1]][i-1];
    for(int i=hd[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        dis[y]=dis[x]+w[i];
        dfs(y,x,d+1);
    }
}
inline int LCA(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=18;i>=0;i--)
        if(dep[f[x][i]]>=dep[y]) 
            x=f[x][i];
    if(x==y) return x;
    for(int i=18;i>=0;i--) 
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline LL path(int x,int y) {
    return dis[x]+dis[y]-2*dis[LCA(x,y)];
}

set<int>s;
bool vis[N];
LL ans;
int main() {
    n=read();m=read(); 
    for(int i=1,x,y,z;i<n;i++) {
        x=read();y=read();z=read();
        add(x,y,z),add(y,x,z);
    }
    dfs(1,0,1);
    for(int i=1,x;i<=m;i++) {
        x=read();
        if(vis[x]) {//del
            s.erase(dfn[x]);
            if(s.empty()) {puts("0");continue;}
            set<int>::iterator l=--s.lower_bound(dfn[x]);
            set<int>::iterator r=s.lower_bound(dfn[x]);
            if(r==s.end()) r=s.begin();
            if(r==s.begin()) l=--s.end();
            ans+=path(rev[*l],rev[*r]);
            ans-=path(rev[*l],x);
            ans-=path(x,rev[*r]);
        } else {//add
            if(s.empty()) {s.insert(dfn[x]);puts("0");continue;}
            set<int>::iterator l=--s.lower_bound(dfn[x]);
            set<int>::iterator r=s.lower_bound(dfn[x]);
            if(r==s.end()) r=s.begin();
            if(r==s.begin()) l=--s.end();
            ans-=path(rev[*l],rev[*r]);
            ans+=path(rev[*l],x);
            ans+=path(x,rev[*r]);
            s.insert(dfn[x]);
        }
        printf("%lld\n",ans);
        vis[x]^=1;
    }
    return 0;
}
2020/8/26 11:08
加载中...