/*********--LCA模板--***************/ //设置好静态参数并构建好图的邻接表，然后调用lca_setquery()设置查询 //最后调用lca_start()，在lca::dfs中的your code处理每次查询 //复杂度O(M+Q) //表示图的邻接表 #define N 40100 #define MAX_Q 200 struct node { int to,next,w; }edge[2*N]; int pre[N],cnt; int ans[MAX_Q]; void add_edge(int u,int v,int w) { edge[cnt].w = w; edge[cnt].to = v; edge[cnt].next =pre[u]; pre[u] = cnt++; } struct LCA { int ln;//表示图中的点,默认范围为[1,n] int bin[N],bw[N]; // 并查集 与 bw记录到根节点的深度 struct node1 { int to,next; int id; }edge1[MAX_Q*2]; int pre1[N],cnt1; int lmark[N]; void init(int n)//初始化传入点的个数n { ln = n; cnt1 = 0; memset(pre1,-1,sizeof(pre1)); memset(lmark,0,sizeof(lmark)); for(int i=0;i<=n;i++) bin[i] = i; } void add_edge1(int u,int v,int id) { edge1[cnt1].id = id;//查询的id edge1[cnt1].to = v; edge1[cnt1].next = pre1[u]; pre1[u]=cnt1++; } int find(int v) { if(bin[v]==v) return v; return bin[v]=find(bin[v]); } void lca_setquery(int m) { //把所有的查询加入 //add_edge1(a,b); //add_edge1(b,a); for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); add_edge1(a,b,i); add_edge1(b,a,i); } } void dfs(int s,int w,int fa) { bw[s]=w; for(int p=pre[s];p!=-1;p=edge[p].next) { int v=edge[p].to; if(v == fa) continue;//不到父亲节点 if(lmark[v]==0) { //dfs(v,w+1,s); dfs(v,w+edge[p].w,s); bin[v]=s; } } lmark[s] = 1; //遍历需要查询的点对 for(int p=pre1[s];p!=-1;p=edge1[p].next) { int v = edge1[p].to; if(lmark[v] == 1)//这个点已经处理过了 { int x = find(v); //最近公共祖先 int dis = bw[v]-bw[x]+bw[s]-bw[x];//两点之间在树上最近距离（这里默认树边为1） // your code //ans[ edge1[p].id ] = dis; // } } } void lca_start() { dfs(1,0,-1);//第一个参数表示根节点 } }lca; //给出大小为n的树，查询m次两点最短距离 //int main() //{ // int T; // cin>>T; // while(T--) // { // int n,m; // scanf("%d%d",&n,&m); // cnt = 0; // memset(pre,-1,sizeof(pre)); // for(int i=1;i<n;i++) // { // int a,b,c; // scanf("%d%d%d",&a,&b,&c); // add_edge(a,b,c); // add_edge(b,a,c); // } // // lca.init(n); // lca.lca_setquery(m); // lca.lca_start(); // for(int i=0;i<m;i++) printf("%d\n",ans[i]); // } // return 0; //}
2.LCA 在线建立rmq（nlog(n)） 查询(log(n))
#define N 40040 #define LN 20 struct node { int to,next; }edge[2*N]; int cnt,pre[N]; void add_edge(int u,int v) { edge[cnt].to = v; edge[cnt].next = pre[u]; pre[u] = cnt++; } struct Lca_Online { int _n; int deep[N]; int dp[N][LN]; void _dfs(int s,int fa,int dd) { deep[s] = dd; for(int p=pre[s];p!=-1;p=edge[p].next) { int v = edge[p].to; if(v == fa) continue; _dfs(v,s,dd+1); dp[v][0] = s; } } void _init() { for(int j=1;(1<<j)<=_n;j++) { for(int i=1;i<=_n;i++) { if(dp[i][j-1]!=-1) dp[i][j] = dp[ dp[i][j-1] ][j-1]; } } } void lca_init(int n) { _n = n; memset(dp,-1,sizeof(dp)); //_dfs(firstid,-1,0); _dfs(1,-1,0); _init(); } int lca_query(int a,int b) { if(deep[a]>deep[b]) swap(a,b); //调整b到a的同一高度 for(int i=LN-1;deep[b]>deep[a];i--) if(deep[b]-(1<<i) >= deep[a]) b = dp[b][i]; if(a == b) return a; for(int i=LN-1;i>=0;i--) { if(dp[a][i]!=dp[b][i]) a = dp[a][i],b = dp[b][i]; } return dp[a][0]; } }lca; //int d[N]; //int main(int argc, const char * argv[]) { // int T; // cin>>T; // while(T--) // { // memset(d,0,sizeof(d)); // cnt = 0; // memset(pre,-1,sizeof(pre)); // int n; // scanf("%d",&n); // for(int i=1;i<n;i++) // { // int a,b; // scanf("%d%d",&a,&b); // add_edge(a, b); // add_edge(b, a); // d[b]++; // } // for(int i=1;i<=n;i++) // { // if(d[i] == 0) firstid = i; // } // int a,b; // cin>>a>>b; // lca.lca_init(n); // printf("%d\n",lca.lca_query(a, b)); // } // return 0; //}