Codevs 1036 商务旅行

 #include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,x,y,ans=,tot=,last[maxn],dep[maxn],p[maxn][];
struct edge{
int to,pre;
}e[maxn<<]; void read(int &k){
k=; int f=; char c=getchar();
while (c<''||c>'')c=='-'&&(f=-),c=getchar();
while (''<=c&&c<='')k=k*+c-'',c=getchar();
k*=f;
}
void add(int x,int y){
e[++tot].to=y;
e[tot].pre=last[x];
last[x]=tot;
}
void dfs(int u,int fa){
dep[u]=dep[fa]+; p[u][]=fa;
for (int i=;i<=log2(dep[u]);i++) p[u][i]=p[p[u][i-]][i-];
for (int i=last[u],to=e[i].to;i;i=e[i].pre,to=e[i].to)
if (to!=fa) dfs(to,u);
}
int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
if (dep[x]>dep[y])
for (int i=log2(dep[x]-dep[y]+);i>=,dep[x]!=dep[y];i--)
if (dep[p[x][i]]>=dep[y]) x=p[x][i];
if (x==y) return x;
for (int i=log2(dep[x]);i>=;i--)
if (p[x][i]!=p[y][i]) x=p[x][i],y=p[y][i];
return p[x][];
}
int main(){
read(n);
for (int i=;i<n;i++){
read(x); read(y);
add(x,y); add(y,x);
}
dfs(,);
read(m); read(x);
for (int i=;i<m;i++){
read(y);
ans+=dep[x]+dep[y]-(dep[lca(x,y)]<<);
x=y;
}
printf("%d\n",ans);
return ;
}

最新文章

  1. 《连载 | 物联网框架ServerSuperIO教程》- 8.单例通讯模式开发及注意事项
  2. iOS学习10之OC类和对象
  3. 【poj3070】 Fibonacci
  4. iOS-打包成ipa
  5. Java 数据结构之Stack
  6. C#下利用封包、拆包原理解决Socket粘包、半包问题(新手篇)
  7. Android开源项目发现---Spinner选择器与日历选择器篇(持续更新)
  8. java字符串函数及理解
  9. 用java读写properties文件的代码
  10. shell脚本练习题
  11. C# 函数式编程 —— 使用 Lambda 表达式编写递归函数
  12. Java并发编程阅读笔记-锁和活跃性问题
  13. Python应用——自定义函数:分割PDF文件函数
  14. js中字符串和正则相关的方法
  15. PYTHON-匿名函数,递归与二分法,面向过程编程
  16. ACM-ICPC 2018 焦作赛区网络预赛- G:Give Candies(费马小定理,快速幂)
  17. python的metaclass浅析-乾颐堂
  18. 超全超详细的 ADB 用法大全
  19. 钉钉开发笔记(三)MySQL的配置
  20. C 和 C++ 字符串函数操作

热门文章

  1. centOS封装
  2. 佛祖保佑 永无bug 代码注释
  3. (进制)51NOD 1057 N的阶乘
  4. C# 树次结构的数据
  5. USB接口大百科:看完你就分得清充电线了
  6. 【转】Java实现将文件或者文件夹压缩成zip
  7. Python之双色球选购和三级菜单问题
  8. [ HDOJ 3826 ] Squarefree number
  9. div常用效果方法-transform
  10. [转帖]关于flask-login中各种API使用实例