bzoj3991 lca+dfs序应用+set综合应用

时间:2021-07-02 10:33:58
/*
给定一棵树,树上会出现宝物,也会有宝物消失
规定如果要收集树上所有宝物,就要选择一个点开始,到每个宝物点都跑一次,然后再回到那个点
现在给定m次修改,每次修改后树上就有一个宝物消失,或者一个宝物出现
请问在这次操作后,按规则跑一次找到所有宝物的最短路径长度 显然按规则跑一次找宝物经过的路径长度,就是从根节点开始dfs一次这些点再回到根节点的路径长度
那么需要将这条路径分解:
将宝物所在点按dfs序依次排列,收尾相接形成一个环
总路径就是环上相邻两点的路径之和
那么每次在环中加入一个点,只要找到环中和其dfs相邻的两个点,加入两条路径即可,删除原来的一条路径即可
每次在环中删掉一个点同理
在增删的过程中保存dfs升序,用set维护结点的dfs即可
*/
#include<bits/stdc++.h>
#include<set>
using namespace std;
#define maxn 100005
#define ll long long
struct Edge{ll to,nxt,w;}edge[maxn<<];
int head[maxn],tot,n,m;
set<int>s;//存储存在宝箱的点的dfs序
set<int>::iterator it;
int cnt,pos[maxn],id[maxn];//每个点的dfs序,dfs序对应的点
ll ans;
void init(){
memset(head,-,sizeof head);
tot=;
}
void addedge(int u,int v,int w){
edge[tot].nxt=head[u];edge[tot].w=w;edge[tot].to=v;head[u]=tot++;
}
void dfs(int u,int pre){
pos[u]=++cnt;id[cnt]=u;
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(v!=pre)dfs(v,u);
}
} int d[maxn],f[maxn][];
ll dep[maxn];
void bfs(){
queue<int>q;
q.push();
d[]=;dep[]=;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(d[v])continue;
d[v]=d[x]+;
dep[v]=dep[x]+edge[i].w;
f[v][]=x;
for(int k=;k<=;k++)
f[v][k]=f[f[v][k-]][k-];
q.push(v);
}
}
}
ll lca(int u,int v){
int x=u,y=v;
if(d[u]<d[v])swap(u,v);
for(int i=;i>=;i--)
if(d[f[u][i]]>=d[v])u=f[u][i];
if(u==v){
return abs(dep[x]-dep[y]);
}
for(int i=;i>=;i--)
if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
u=f[u][];
return (dep[x]+dep[y]-*dep[u]);
} int flag[maxn];
int L(int x){//返回x左边的结点
it=s.lower_bound(pos[x]);
if(it==s.begin())it=s.end();
--it;
return id[*it];
}
int R(int x){//返回x右边的结点
it=s.lower_bound(pos[x]);
++it;
if(it==s.end())it=s.begin();
return id[*it];
}
ll query(int x){
int mul,left,right;
if(flag[x]==){//往集合里加入结点
flag[x]=mul=;
s.insert(pos[x]);
left=L(x);right=R(x);
}
else {//把集合里的结点删了
flag[x]=;mul=-;
left=L(x);right=R(x);
s.erase(pos[x]);
}
if(s.size()==)return ;
ans+=(ll)mul*(lca(left,x)+lca(x,right)-lca(left,right));
return ans;
}
int main(){
init();
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
ll u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
dfs(,);//求出dfs序
bfs();//预处理
for(int i=;i<=m;i++){
int x,u,v;
scanf("%d",&x);
printf("%lld\n",query(x));
}
}