模板最近的共同祖先-白红宇

模板最近的共同祖先

阅读量：7217 次

发布时间：2019-06-29

本文共 3770 字，大约阅读时间需要 12 分钟。

LCA tarjan 离线算法

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 40010;int first[maxn], head[maxn], cnt, sum;struct edge{	int u, v, w, next;}e[maxn*2], qe[maxn], Q[maxn];int ans[maxn];int f[maxn], vis[maxn];int d[maxn];void AddEdge(int u, int v, int w){	e[cnt].u = u;	e[cnt].v = v;	e[cnt].w = w;	e[cnt].next = first[u];	first[u] = cnt++;	e[cnt].u = v;	e[cnt].v = u;	e[cnt].w = w;	e[cnt].next = first[v];	first[v] = cnt++;}int find(int x){	if(f[x] != x)		return f[x] = find(f[x]);	return f[x];}void LCA(int u, int k){	f[u] = u;	d[u] = k;	vis[u] = true;	for(int i = first[u]; i != -1; i = e[i].next)	{		int v = e[i].v;		if(vis[v])			continue;			LCA(v, k + e[i].w);		f[v] = u;	}	for(int i = head[u]; i != -1; i = qe[i].next)	{		int v = qe[i].v;		if(vis[v])		{			ans[qe[i].w] = find(v);		}	}}

LCA 转RMQ的在线算法

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 200010;struct edge{	int u, v, w, next;}edges[maxn*2], e[maxn];int E[maxn*2], H[maxn*2], I[maxn*2], L[maxn], R[maxn];int dp[maxn*2][40];int cnt, clock, dfn;int first[maxn];int a[maxn<<2];int b[maxn];int add[maxn<<2];int degree[maxn];int vis[maxn];void AddEdge(int u, int v, int w){	edges[cnt].u = u;	edges[cnt].v = v;	edges[cnt].w = w;	edges[cnt].next = first[u];	first[u] = cnt++;	edges[cnt].u = v;	edges[cnt].v = u;	edges[cnt].w = w;	edges[cnt].next = first[v];	first[v] = cnt++;	}void dfs(int u, int fa, int dep){	E[++clock] = u;	H[clock] = dep;	I[u] = clock;	L[u] = ++dfn;	b[dfn] = u;	for(int i = first[u]; i != -1; i = edges[i].next)	{		int v = edges[i].v;		if(v == fa)			continue;		if(vis[v])			continue;		vis[v] = true;		dfs(v, u, dep+1);		E[++clock] = u;		H[clock] = dep;	}	R[u] = dfn;}void RMQ_init(int n){	for(int i = 1; i <= n; i++)		dp[i][0] = i;	for(int j = 1; (1<
        
         <= n; j++)		for(int i = 1; i+(1<
         
          <= n; i++)		{			if(H[dp[i][j-1]] < H[dp[i+(1<<(j-1))][j-1]])				dp[i][j] = dp[i][j-1];			else				dp[i][j] = dp[i+(1<<(j-1))][j-1];		}}int RMQ(int l, int r){	l = I[l], r = I[r];	if(l > r)		swap(l, r);	int len = r-l+1, k = 0;	while((1<
          
           <= len) k++; k--; if(H[dp[l][k]] < H[dp[r-(1<

LCA倍增法

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 20010;const int INF = 999999999;int anc[maxn][16], maxcost[maxn][16];int fa[maxn], L[maxn], cost[maxn], vis[maxn];int n, m;int first[maxn], cnt;struct edge{	int u, v, next;}e[maxn*2];void AddEdge(int u, int v){	e[cnt].v = v;	e[cnt].next = first[u];	first[u] = cnt++;	e[cnt].v = u;	e[cnt].next = first[v];	first[v] = cnt++;}void pre(){	for(int i = 1; i <= n; i++)	{		anc[i][0] = fa[i]; maxcost[i][0] = cost[i];		for(int j = 1; (1<
        
         < n; j++)			anc[i][j] = -1;	}	for(int j = 1; (1<
         
          < n; j++)		for(int i = 1; i <= n; i++)			if(anc[i][j-1] != -1)			{				int a = anc[i][j-1];				anc[i][j] = anc[a][j-1];				maxcost[i][j] = max(maxcost[i][j-1], maxcost[a][j-1]);			}	}int query(int p, int q){	int tmp, log, i;	if(L[p] < L[q])		swap(p, q);	for(log = 1; (1<
          
           <= L[p]; log++); log--; int ans = -INF; for(int i = log; i >= 0; i--) if(L[p] - (1<
           
            = L[q]) { ans = max(ans, maxcost[p][i]); p = anc[p][i]; } if(p == q) return ans; for(int i = log; i >= 0; i--) { if(anc[p][i] != -1 && anc[p][i] != anc[q][i]) { ans = max(ans, maxcost[p][i]); ans = max(ans, maxcost[q][i]); p = anc[p][i]; q = anc[q][i]; } } ans = max(ans, cost[p]); ans = max(ans, cost[q]); return ans;}void dfs(int u){ for(int i = first[u]; i != -1; i = e2[i].next) { int v = e[i].v; if(vis[v]) continue; vis[v] = 1; fa[v] = u; L[v] = L[u]+1; dfs(v); }}