欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【JZOJ A组】火车

程序员文章站 2024-02-11 13:23:46
...

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

9

Data Constraint

【JZOJ A组】火车

思路

一开始我还理解错题意了。。。

我们需要判断这些点是否走过,可以用并查集判断(把路径上所有点合并)。

注意建树时要用bfs,否则会栈溢出

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=5e5+77;
int f[maxn][22],n,m,s,d[maxn],list[maxn],cnt=0,fa[maxn];
long long ans=0;
struct E
{
    int to,next;
}e[maxn*2];
void add(int u,int v)
{
    e[++cnt].to=v; e[cnt].next=list[u]; list[u]=cnt;
}
void bfs(int u,int fa)
{
    queue<int> qu,qf;
    f[u][0]=fa; d[u]=d[fa]+1;
    qu.push(u); qf.push(fa);
    while(!qu.empty())
    {
        u=qu.front(); fa=qf.front(); qu.pop(); qf.pop();
        for(int i=list[u]; i; i=e[i].next)
        {
            int v=e[i].to;
            if(v==fa) continue;
            d[v]=d[u]+1; f[v][0]=u;
            qu.push(v); qf.push(u);
        }
    }
/*  for(int i=list[u]; i; i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
    }*/
}
int get_lca(int u,int v)
{
    int dep,x=u,y=v;
    if(d[u]<d[v]) swap(u,v);
    int p=d[u]-d[v];
    if(p) for(int i=0; i<=log2(n)+1&&p; i++,p>>=1) if(p&1) u=f[u][i];
    if (u==v) return u;else
    {
        for(int i=log2(n)+1; i>=0; i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
        return f[u][0];
    }
}
int gf(int x)
{
    return fa[x]==x?x:fa[x]=gf(fa[x]);
}
int main()
{
    freopen("train.in","r",stdin); freopen("train.out","w",stdout);
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1; i<n; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    d[1]=1;
    bfs(1,0);
    for(int i=1; i<=log2(n)+1; i++)
    {
        for(int j=1; j<=n; j++)
        {
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
    for(int i=1; i<=n; i++) fa[i]=i;
    for(int i=1; i<=m; i++)
    {
        int x;
        scanf("%d",&x);
        int u=gf(x),v=gf(s);
        if(u==v) continue;
        int lca=get_lca(s,x);
        ans+=d[s]+d[x]-1ll*2*d[lca];
        u=x,v=s; int flca=gf(lca);
        while(gf(u)!=flca)
        {
            int t=gf(u); fa[t]=flca; u=f[t][0];
        }
        while(gf(v)!=flca)
        {
            int t=gf(v); fa[t]=flca; v=f[t][0];
        }
        s=x;
    }
    printf("%lld",ans);
}