mxqz 样例能过,开了ll,WA0pts
查看原帖
mxqz 样例能过,开了ll,WA0pts
939998
Sheez楼主2023/5/16 07:56

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct edge{int nex,val;};
int n,m,ans=0;
int f[20][N],dep[N],dis[N],dfn[N],nfd[N];
bool tre[N];
vector<edge>e[N];
set<int>S;set<int>::iterator it;
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;dfn[++dfn[0]]=u;nfd[u]=dfn[0];
    for(int i=1;(1<<i)<=dep[u];i++)f[i][u]=f[i-1][f[i-1][u]];
    for(auto x:e[u])if(x.nex!=fa)f[0][x.nex]=u,dis[x.nex]=dis[u]+x.val,dfs(x.nex,u);
    return;
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=18;i>=0;i--){if(dep[f[i][x]]>=dep[y])x=f[i][x];if(x==y)return x;}
    for(int i=18;i>=0;i--)if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];
    return f[0][x];
}
int dist(int x,int y)
{
    return dis[x]+dis[y]-(dis[lca(x,y)]<<1);
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        e[x].push_back({y,z});e[y].push_back({x,z});
    }
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        int pos;scanf("%lld",&pos);pos=dfn[pos];
        if(!tre[nfd[pos]])S.insert(pos);
        int x=nfd[(it=S.lower_bound(pos))==S.begin()?*--S.end():*--it];
        int y=nfd[(it=S.upper_bound(pos))==S.end()?*S.begin():*it];
        if(tre[nfd[pos]])S.erase(pos);
        pos=nfd[pos];
        int len=dist(x,pos)+dist(pos,y)-dist(x,y);
        // printf("%d %d %d\n",x,y,len);
        if(tre[pos])tre[pos]=0,ans-=len;
        else tre[pos]=1,ans+=len;
        printf("%lld\n",ans);
    }
    return 0;
}
2023/5/16 07:56
加载中...