思路:

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);
}

最新文章

  1. python django基础(二)
  2. android之旋转的刻度盘
  3. 不用Unity库,利用.NET动态代理自己实现AOP
  4. MoveManager管理类
  5. ECshop Strict Standards: Only variables should be passed by reference in解决办法
  6. NOIP2001 一元三次方程求解
  7. [您有新的未分配科技点]无旋treap:从好奇到入门(例题:bzoj3224 普通平衡树)
  8. Mysql 的 IF 判断
  9. selenium自动化测试打开新标签窗口
  10. 纯css提示效果 提示层
  11. SSL,TLS
  12. Inception部署
  13. 《2018面向对象程序设计(Java)课程学习进度条》
  14. JS基础概念
  15. 学会数据库读写分离、分表分库——用Mycat
  16. 团队项目第二周spec设计
  17. thinkphp验证码的使用
  18. ES7 async 函数
  19. android 开发第三库
  20. BZOJ 1005: [HNOI2008]明明的烦恼(prufer数列)

热门文章

  1. 1、Scala安装与基础
  2. 团体程序设计天梯赛-练习集-L1-038. 新世界
  3. Axure RP 9 WIN10 64位安装步骤及注册码
  4. ptyhon获取app设备号、包名、activity
  5. 慕课网页面app的滑动
  6. 数据类型----&gt;Number
  7. 在LINUX系统上通过LINUX命令安装mysql数据库和JDK环境
  8. ScrollReveal-元素随页面滚动产生动画的js插件
  9. python第十一周:RabbitMQ、Redis
  10. 继续过Hard题目