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

/* 给定一棵树，树上会出现宝物，也会有宝物消失 规定如果要收集树上所有宝物，就要选择一个点开始，到每个宝物点都跑一次，然后再回到那个点 现在给定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<<1]; 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,-1,sizeof head); tot=0; } 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!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v!=pre)dfs(v,u); } } int d[maxn],f[maxn][30]; ll dep[maxn]; void bfs(){ queue<int>q; q.push(1); d[1]=1;dep[1]=0; while(!q.empty()){ int x=q.front();q.pop(); for(int i=head[x];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(d[v])continue; d[v]=d[x]+1; dep[v]=dep[x]+edge[i].w; f[v][0]=x; for(int k=1;k<=29;k++) f[v][k]=f[f[v][k-1]][k-1]; 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=29;i>=0;i--) if(d[f[u][i]]>=d[v])u=f[u][i]; if(u==v){ return abs(dep[x]-dep[y]); } for(int i=29;i>=0;i--) if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i]; u=f[u][0]; return (dep[x]+dep[y]-2*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]==0){//往集合里加入结点 flag[x]=mul=1; s.insert(pos[x]); left=L(x);right=R(x); } else {//把集合里的结点删了 flag[x]=0;mul=-1; left=L(x);right=R(x); s.erase(pos[x]); } if(s.size()==1)return 0; 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=1;i<n;i++){ ll u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dfs(1,0);//求出dfs序 bfs();//预处理 for(int i=1;i<=m;i++){ int x,u,v; scanf("%d",&x); printf("%lld\n",query(x)); } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10512850.html

相关资源：各显卡算力对照表！