BZOJ 3910: 火车

3910: 火车

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 358 Solved: 130
[Submit][Status][Discuss]

Description

A 国有n 个城市，城市之间有一些双向道路相连，并且城市两两之间有唯一

路径。现在有火车在城市 a，需要经过m 个城市。火车按照以下规则行驶：每次

行驶到还没有经过的城市中在 m 个城市中最靠前的。现在小 A 想知道火车经过

这m 个城市后所经过的道路数量。

Input

第一行三个整数 n、m、a，表示城市数量、需要经过的城市数量，火车开始

时所在位置。

接下来 n-1 行，每行两个整数 x和y，表示 x 和y之间有一条双向道路。

接下来一行 m 个整数，表示需要经过的城市。

Output

一行一个整数，表示火车经过的道路数量。

Sample Input

5 4 2
1 2
2 3
3 4
4 5
4 3 1 5

Sample Output

HINT

N<=500000 ,M<=400000

Source

分析：

在经历了无数次对题意的错误理解(和被YouSiki的无数次吐槽)之后，我理解对了题意，然后觉得可能是个暴力...

事实证明这就是个暴力，我们每一次暴力标记访问过的节点，然后并查集维护，如果访问过就把这个点并到父亲上，均摊复杂度显然是$O(N)$的...

代码：

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

//by NeighThorn

using namespace std;

const int maxn=500000+5;

int n,m,st,cnt,a[maxn],f[maxn],hd[maxn],to[maxn<<1],fa[maxn][25],dep[maxn],nxt[maxn<<1];

long long ans;

inline int find(int x){

	return f[x]==x?x:f[x]=find(f[x]);

}

inline void add(int x,int y){

	to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;

}

inline void dfs(int x){

	for(int i=hd[x];i!=-1;i=nxt[i])

		if(to[i]!=fa[x][0])

			fa[to[i]][0]=x,

			dep[to[i]]=dep[x]+1,dfs(to[i]);

}

inline void init(void){

	for(int j=1;j<=20;j++)

		for(int i=1;i<=n;i++)

			fa[i][j]=fa[fa[i][j-1]][j-1];

}

inline int LCA(int x,int y){

	if(dep[x]<dep[y])

		swap(x,y);

	int d=dep[x]-dep[y];

	for(int i=20;i>=0;i--)

		if((d>>i)&1)

			x=fa[x][i];

	if(x==y)

		return x;

	for(int i=20;i>=0;i--)

		if(fa[x][i]!=fa[y][i])

			x=fa[x][i],y=fa[y][i];

	return fa[x][0];

}

signed main(void){

	memset(hd,-1,sizeof(hd));

	scanf("%d%d%d",&n,&m,&st);

	for(int i=1,x,y;i<n;i++)

		scanf("%d%d",&x,&y),add(x,y),add(y,x);

	dep[1]=1,fa[1][0]=1,dfs(1);init();

	for(int i=1;i<=n;i++)

		f[i]=i;

	for(int i=1;i<=m;i++)

		scanf("%d",&a[i]);

	for(int i=1,x,y,lca;i<=m;i++){

		if(find(a[i])!=a[i])

			continue;

		x=st,y=a[i],lca=LCA(x,y);

		while(dep[x]>=dep[lca]){

			if(find(x)==x)

				f[x]=x==1?0:fa[x][0];

			else

				x=find(x);

		}

		while(dep[y]>=dep[lca]){

			if(find(y)==y)

				f[y]=y==1?0:fa[y][0];

			else

				y=find(y);

		}

		x=st,y=a[i],st=a[i];

		ans+=dep[x]-dep[lca];

		ans+=dep[y]-dep[lca];

	}

	printf("%lld\n",ans);

	return 0;

}

By NeighThorn

巴特西