LCA(最近公共祖先)模板

时间：2022-03-08 11:03:27

　　Tarjan版本

/*  gyt

       Live up to every day            */

#pragma comment(linker,"/STACK:1024000000,1024000000")

#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<cstring>

#include<queue>

#include<set>

#include<string>

#include<map>

#include <time.h>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = 1e5+;

const ll maxm = 1e7;

const ll base = ;

const int INF = <<;

const db eps = 1e-;

const ll mod = 1e9+;

struct Edge{

    int u, v, next, val;

}edge[maxn*], edge1[maxn*];

int n, m;

int head[maxn], head1[maxn];

int father[maxn], dis[maxn], tol, toll, LCA[maxn];

bool visit[maxn];

int cnt;

//LCA[]最近公共祖先

void init() {

    cnt=;

    memset(head, -, sizeof(head));

    memset(head1, -, sizeof(head1));

    tol=toll=;

    memset(visit, , sizeof(visit));

    memset(LCA, , sizeof(LCA));

    memset(dis, , sizeof(dis));

}

void add(int u, int v, int w) {

    edge[tol].u=u, edge[tol].v=v,edge[tol].val=w;

    edge[tol].next=head[u];

    head[u]=tol++;

}

void add1(int u, int v, int w) {

    edge1[toll].u=u, edge1[toll].v=v,edge1[toll].val=w;

    edge1[toll].next=head1[u];

    head1[u]=toll++;

}

int Find(int x) {

    if (x!=father[x])  father[x]=Find(father[x]);

    return father[x];

}

void tarjan(int u) {

    visit[u]=;

    father[u]=u;

    for (int j=head1[u]; ~j; j=edge1[j].next) {

        int v=edge1[j].v;

        if (visit[v])  LCA[edge1[j].val]=Find(v);

    }

    for (int j=head[u]; ~j; j=edge[j].next) {

        int v=edge[j].v;

        if (!visit[v]) {

            dis[v]=dis[u]+edge[j].val;

            tarjan(v);

            father[v]=u;

            //cout<<dis[v]<<endl;

        }

    }

}

void solve() {

    init();

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

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

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

        add(a, b, c);  add(b, a, c);

    }

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

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

        add1(a, b, i);  add1(b, a, i);

    }

    dis[]=;

    tarjan();

    for(int i=;i<toll;i+=){

        printf("%d\n",LCA[edge1[i].val]);

    }

}

int main() {

    int t = ;

    //freopen("in.txt","r",stdin);

  //  freopen("gcd.out","w",stdout);

     scanf("%d", &t);

    while(t--)

        solve();

    return ;

}

　　倍增版本

/*  gyt

       Live up to every day            */

#pragma comment(linker,"/STACK:1024000000,1024000000")

#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<cstring>

#include<queue>

#include<set>

#include<string>

#include<map>

#include <time.h>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = 1e5+;

const ll maxm = 1e7;

const ll base = ;

const int INF = <<;

const db eps = 1e-;

const ll mod = 1e9+;

struct Edge{

    int u, v, next, val;

}edge[maxn*];

int head[maxn], dis[maxn];

int f[maxn], deep[maxn], p[maxn][];

int n, m, cnt;

void init() {

    int i,j;

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

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

        p[i][j]=-;

    for(i=;i<=n;i++)p[i][]=f[i];

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

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

        if(p[i][j-]!=-)

        p[i][j]=p[p[i][j-]][j-];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先

}

void add(int u, int v, int w) {

    edge[cnt].u=u, edge[cnt].v=v;

    edge[cnt].next=head[u], edge[cnt].val=w;

    head[u]=cnt++;

}

void dfs(int u, int pre, int t) {

    deep[u]=t;

    f[u]=pre;

    for (int i=head[u]; ~i; i=edge[i].next) {

        int v=edge[i].v;

       if (v!=pre) {

        dis[v]=dis[u]+edge[i].val;

        dfs(v, u, t+);

       }

    }

}

int lca(int a, int b) {

    int i, j;

    if (deep[a]<deep[b])  swap(a, b);

    for ( i=; (<<i)<=deep[a]; i++);

    i--;

    for ( j=i; j>=; j--) {

        if (deep[a]-(<<j)>=deep[b])  a=p[a][j];

    }

    if (a==b)  return a;

    for ( j=i; j>=; j--) {

        if (p[a][j]!=- && p[a][j]!=p[b][j]) {

            a=p[a][j], b=p[b][j];

        }

    }

    return f[a];

}

void solve() {

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

    cnt=;

    memset(head, -, sizeof(head));

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

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

        add(a, b, c);  add(b, a, c);

    }

    dis[]=;

    dfs(, -, );

    init();

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

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

        int ans=dis[a]+dis[b]-*dis[lca(a, b)];

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

    }

}

int main() {

    int t = ;

   // freopen("in.txt","r",stdin);

  //  freopen("gcd.out","w",stdout);

     scanf("%d", &t);

    while(t--)

        solve();

    return ;

}

相关文章