题目描述 Description
某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。
假设有N个城镇，首都编号为1，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环。
你的任务是帮助该商人计算一下他的最短旅行时间。
输入描述 Input Description
输入文件中的第一行有一个整数N，1<=n<=30 000，为城镇的数目。下面N-1行，每行由两个整数a 和b (1<=a, b<=n; a<>b)组成，表示城镇a和城镇b有公路连接。在第N+1行为一个整数M，下面的M行，每行有该商人需要顺次经过的各城镇编号。
输出描述 Output Description
在输出文件中输出该商人旅行的最短时间。
样例输入 Sample Input
5
1 2
1 5
3 5
4 5
4
1
3
2
5
样例输出 Sample Output
7
数据范围及提示 Data Size & Hint
题解：
倍增：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=30000+5; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,num,ans; int head[maxn],dep[maxn],f[maxn][20]; bool vis[maxn]; struct node { int next,to; }e[maxn<<1]; void add(int from,int to) { e[++num].next=head[from]; e[num].to=to; head[from]=num; } void dfs(int x,int d) { vis[x]=1;dep[x]=d; for(int i=head[x];i;i=e[i].next) { int to=e[i].to; if(!vis[to]) { f[to][0]=x; dfs(to,d+1); } } } int lca(int a,int b) { if(dep[a]<dep[b]){int t=a;a=b;b=t;} int d=dep[a]-dep[b]; for(int i=0;i<=15;i++) if(d&(1<<i)) a=f[a][i]; if(a==b) return a; for(int i=15;i>=0;i--) if(f[a][i]!=f[b][i]) { a=f[a][i]; b=f[b][i]; } return f[a][0]; } int main() { n=read(); for(int i=1;i<n;i++) { int x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(1,1); for(int j=1;j<=15;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; m=read(); int x=1,y; for(int i=1;i<=m;i++) { y=read(); ans+=dep[x]+dep[y]-(dep[lca(x,y)]<<1); x=y; } printf("%d ",ans); return 0; }
tarjan算法：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=30000+5; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,num,qnum,ans; int head[maxn],qhead[maxn],father[maxn],dep[maxn],f[maxn][20],a[maxn][3]; bool vis[maxn]; struct node { int next,to; }e[maxn<<1]; struct qnode { int next,to,k; }q[maxn<<1]; void add(int from,int to) { e[++num].next=head[from]; e[num].to=to; head[from]=num; } void qadd(int from,int to,int k) { q[++qnum].next=qhead[from]; q[qnum].to=to; q[qnum].k=k; qhead[from]=qnum; } int find(int x) { if(x!=father[x]) father[x]=find(father[x]); return father[x]; } void merge(int x,int y) { int r1=find(x); int r2=find(y); father[r1]=r2; } void tarjan(int x) { vis[x]=1; for(int i=qhead[x];i;i=q[i].next) { int to=q[i].to,k=q[i].k; if(vis[to]) a[k][2]=find(to); } for(int i=head[x];i;i=e[i].next) { int to=e[i].to; if(!vis[to]) { dep[to]=dep[x]+1; tarjan(to); merge(to,x); } } } int main() { n=read(); for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<n;i++) { int x,y; x=read();y=read(); add(x,y);add(y,x); } m=read(); int x=1,y; for(int i=1;i<=m;i++) { y=read(); a[i][0]=x;a[i][1]=y; qadd(x,y,i);qadd(y,x,i); x=y; } tarjan(1); for(int i=1;i<=m;i++) ans+=dep[a[i][0]]+dep[a[i][1]]-(dep[a[i][2]]<<1); printf("%d ",ans); return 0; }