lca函数C语言用吗,求LCA的三种方法

1.Tarjan O(n+q) HDU - 2586

#include #include #include #include #include #include #include #include #include #define FRER() freopen("in.txt","r",stdin)

#define FREW() freopen("out.txt","w",stdout)

#define go int T;cin>>T;for(int kase=0;kasepii;

const int maxn = 40000 + 7;

int n,m,nEdge;

int to[maxn*2],nxt[maxn*2],w[maxn*2],head[maxn],ans[maxn],d[maxn],f[maxn],vis[maxn];

struct Node {

int to,id;

};

void addEdge(int u,int v,int c){to[nEdge] = v;nxt[nEdge] = head[u];w[nEdge] = c;head[u] = nEdge++;}

int Find(int u){return u==f[u]?u:f[u]=Find(f[u]);}

vectorq[maxn];

void Init(){

nEdge = 0;

memset(d, 0, sizeof(d));

memset(vis, 0, sizeof(vis));

memset(ans, 0, sizeof(ans));

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

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

for(int i=0;i<=n;i++) q[i].clear();

}

void LCA(int u,int dis){

vis[u] = 1;

d[u] = dis;

for(int e=head[u];~e;e=nxt[e]){

int v = to[e];

if(vis[v]) continue;

LCA(v, dis + w[e]);

int uu = Find(u);

int vv = Find(v);

if(uu!=vv)

f[vv] =uu;

}

int len = (int)q[u].size();

for(int i=0;i

2.倍增 O((n+q)logn) ZOJ - 3195

#include #include #include #include #include #include #include #include #include #define FRER() freopen("in.txt","r",stdin)

#define FREW() freopen("out.txt","w",stdout)

#define go int T;cin>>T;for(int kase=0;kasepii;

const int maxn = 50000 + 7;

int n,m,nEdge;

int to[maxn*2],nxt[maxn*2],w[maxn*2],head[maxn],d[maxn],f[maxn],vis[maxn],depth[maxn];

void addEdge(int u,int v,int c){to[nEdge] = v;nxt[nEdge] = head[u];w[nEdge] = c;head[u] = nEdge++;}

void Init(){

nEdge = 0;

memset(d, 0, sizeof(d));

memset(vis, 0, sizeof(vis));

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

}

void dfs(int u,int d1,int d2,int pre){

f[u] = pre;

d[u] = d1;

depth[u] = d2;

vis[u] = 1;

for(int e = head[u];~e;e=nxt[e]){

int v = to[e];

if(vis[v]) continue;

dfs(v, d1+w[e], d2+1,u);

}

}

int LCA(int u,int v){

int uu = u , vv = v;

if(depth[u]>depth[v]) swap(u,v);

while(depth[v]>depth[u]) v = f[v];

while(u!=v){

u = f[u];

v = f[v];

}

return d[uu]+d[vv]-2*d[u];

}

int main(){

//FRER();

//FREW();

int k = 0;

while(~scanf("%d",&n)){

if(k++) cout<

3.RMQ O(nlogn) POJ - 1986

#include #include #include #include #include #include #include #include #include #define FRER() freopen("in.txt","r",stdin)

#define FREW() freopen("out.txt","w",stdout)

#define go int T;cin>>T;for(int kase=0;kasepii;

const int maxn = 50000 + 7;

int n,m,nEdge,tot;

int to[maxn*2],nxt[maxn*2],w[maxn*2],head[maxn],d[maxn],f[maxn],vis[maxn],depth[maxn],st[maxn<<1][20],in[maxn];

void addEdge(int u,int v,int c){to[nEdge] = v;nxt[nEdge] = head[u];w[nEdge] = c;head[u] = nEdge++;}

void Init(){

nEdge = tot = 0;

memset(d, 0, sizeof(d));

memset(vis, 0, sizeof(vis));

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

}

void dfs(int u,int d1,int d2,int pre){

f[u] = pre;

d[u] = d1;

depth[u] = d2;

vis[u] = 1;

st[++tot][0] = u;

in[u] = tot;

for(int e = head[u];~e;e=nxt[e]){

int v = to[e];

if(vis[v]) continue;

dfs(v, d1+w[e], d2+1,u);

st[++tot][0] = u;

}

}

void getST(){

for (int j = 1; (1 << j) <= tot; j++) {

for (int i = 1; i + (1 << j) - 1 <= tot; i++) {

int ans1 = depth[st[i][j - 1]];

int ans2 = depth[st[i + (1 << (j - 1))][j - 1]];

if(ans1in[v]) swap(u, v);

printf("%d\n",d[u]+d[v]-2*d[RMQ(in[u], in[v])]);

}

}

return 0;

}