codevs1036 商务旅行 lcs倍增

2017年03月26日 11点热度 0人点赞 0条评论
题目描述 Description

某首都城市的商人要经常到各城镇去做生意,他们按自己的路线去做,目的是为了更好的节约时间。

假设有N个城镇,首都编号为1,商人从首都出发,其他各城镇之间都有道路连接,任意两个城镇之间如果有直连道路,在他们之间行驶需要花费单位时间。该国公路网络发达,从首都出发能到达任意一个城镇,并且公路网络不会存在环。

你的任务是帮助该商人计算一下他的最短旅行时间。

输入描述 Input Description

输入文件中的第一行有一个整数N,1<=n<=30 000,为城镇的数目。下面N-1行,每行由两个整数a 和b (1<=ab<=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

//lca倍增,又是巧妙的利用了二进制
#include
#include
#include
using namespace std;
const int mx=30010;
vector a[mx];
int n,m,pos,f[mx][25],deep[mx],ans=0;
void dfs(int cur,int fa,int d) {
	deep[cur]=d;
	f[cur][0]=fa;
	for(int i=1; i<16; i++)
		f[cur][i]=f[f[cur][i-1]][i-1];
	for(int i=0; ideep[y]) swap(x,y);//y更深
	for(int i=15; i>=0; i--) {
		//用倍增查到相同深度的两个(祖先)节点
		if(deep[x]<=deep[f[y][i]])//这里的等号可不能少啊
			y=f[y][i];
	}
	if(x==y) return x;
	for(int i=15; i>=0; i--) {
		//用同时倍增查到相同的祖先节点,其实就是一个数可以用二进制表示出来
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	}
	return f[x][0];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	int t1,t2;
	for(int i=1; i>t1>>t2;
		a[t1].push_back(t2);
		a[t2].push_back(t1);
	}
	dfs(1,1,0);//令根节点1的父节点是1
	cin>>m>>pos;
	for(int i=1; i>t1;
		ans+=deep[pos]+deep[t1]-2*deep[lca(pos,t1)];
		pos=t1;
	}
	cout<

未经允许不得转载!codevs1036 商务旅行 lcs倍增

update

纸上得来终觉浅, 绝知此事须躬行。