BZOJ 3910 火车倍增LCA

本题并不需要并查集，每次查询一次最近公共祖先，并倍增求出需要被新标记的路径。

这样保证时间复杂度是 O(nlogn)O(nlogn)O(nlogn) 的。

Code:

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = 500000 + 4;

const int logn  = 21;

int f[25][maxn], head[maxn], to[maxn << 1], nex[maxn << 1], cnt, n, m, s, dep[maxn];

bool  tag[maxn];

long long ans;

inline void add_edge(int u,int v){

    nex[++cnt] = head[u];

    head[u] = cnt;

    to[cnt] = v;

}

void dfs(int u,int fa, int depth)

{

    f[0][u] = fa, dep[u] = depth;

    for(int v = head[u]; v ; v = nex[v]){

        if(to[v] != fa){

            dfs(to[v], u, depth + 1);

        }

    }

}

inline int lca(int a,int b){                         //b向 a 爬

    if(dep[a] > dep[b]) swap(a,b);

    if(dep[a] != dep[b]){

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

            if(dep[f[i][b]] >= dep[a]) b = f[i][b];

    }

    if(a == b) return a;

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

    {

        if(f[i][a] != f[i][b])

        {

            a = f[i][a], b = f[i][b];

        }

    }

    return f[0][a];

}

inline void connect(int a, int b){

    if(tag[a] && tag[b]) return ;

    if(dep[a] < dep[b]) swap(a, b);                                  //a 爬向 b

    int A = a;

    if(tag[A])

    {

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

            if(tag[f[i][a]] == 1 ) a = f[i][a];

    }

    do

    {

        tag[a] = tag[f[0][a]] = 1;

        a = f[0][a];

    }while(a != b);

}

int main(){

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

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

        int a,b;

        scanf("%d%d",&a,&b);

        add_edge(a,b);

        add_edge(b,a);

    }

    dfs(1, 0, 1);

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

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

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

    int pre = s;

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

        int cur;

        scanf("%d",&cur);

        int h = lca(pre, cur);

        if(tag[cur] && tag[pre]) continue;

        ans +=(long long) dep[cur] + dep[pre] - 2 * dep[h];

        connect(pre, h);

        connect(cur, h);

        pre = cur;

    }

    printf("%lld",ans);

    return 0;

}

巴特西

BZOJ 3910 火车倍增LCA

最新文章

热门文章

巴特西

BZOJ 3910 火车 倍增LCA

最新文章

热门文章

BZOJ 3910 火车倍增LCA