BZOJ 3910 并查集+线段树合并
2024-09-07 05:25:05
思路:
1. 并查集+线段树合并
记得f[LCA]==LCA的时候 f[LCA]=fa[LCA]
2.LCT(并不会写啊...)
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=;
int n,m,xx,yy,a,first[N],next[N*],v[N*],tot,deep[N],num[N],f[N],fa[N][];
long long ans;
int lca(int x,int y){
if(deep[x]<deep[y])swap(x,y);
for(int i=;~i;i--)if(deep[x]-(<<i)>=deep[y])x=fa[x][i];
if(x==y)return x;
for(int i=;~i;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][];
}
void dfs(int x){for(int i=first[x];~i;i=next[i])if(v[i]!=fa[x][])deep[v[i]]=deep[x]+,fa[v[i]][]=x,dfs(v[i]);}
void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}
int dis(int x,int y){return deep[x]+deep[y]-*deep[lca(x,y)];}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main(){
memset(first,-,sizeof(first));
scanf("%d%d%d",&n,&m,&a);
for(int i=;i<n;i++){
scanf("%d%d",&xx,&yy),add(xx,yy),add(yy,xx);
}deep[]=,dfs();
for(int j=;j<=;j++)
for(int i=;i<=n;i++)
fa[i][j]=fa[fa[i][j-]][j-];
for(int i=;i<=m;i++)scanf("%d",&num[i]);
for(int i=;i<=n;i++)f[i]=i;
for(int i=;i<=m;i++){
if(find(num[i])==num[i]){
int LCA=lca(a,num[i]);
ans+=dis(a,num[i]);
for(int j=a;deep[j]>deep[LCA];j=find(fa[j][]))f[j]=LCA;
for(int j=num[i];deep[j]>deep[LCA];j=find(fa[j][]))f[j]=LCA;
if(f[LCA]==LCA)f[LCA]=fa[LCA][];
a=num[i];
}
}
printf("%lld\n",ans);
}
最新文章
- python django基础(二)
- android之旋转的刻度盘
- 不用Unity库,利用.NET动态代理自己实现AOP
- MoveManager管理类
- ECshop Strict Standards: Only variables should be passed by reference in解决办法
- NOIP2001 一元三次方程求解
- [您有新的未分配科技点]无旋treap:从好奇到入门(例题:bzoj3224 普通平衡树)
- Mysql 的 IF 判断
- selenium自动化测试打开新标签窗口
- 纯css提示效果 提示层
- SSL,TLS
- Inception部署
- 《2018面向对象程序设计(Java)课程学习进度条》
- JS基础概念
- 学会数据库读写分离、分表分库——用Mycat
- 团队项目第二周spec设计
- thinkphp验证码的使用
- ES7 async 函数
- android 开发第三库
- BZOJ 1005: [HNOI2008]明明的烦恼(prufer数列)