BB
众所周知,LCA有N种方法。一种种慢慢学。。。
方法
1. 倍增求法
2. 待续...
Problem List
//POJ 1986 lca模板 #include<bits/stdc++.h> using namespace std; const int maxn=4e4+5; struct Edge{ int to; int len; }; vector<Edge> G[maxn]; int fa[maxn][21],dep[maxn],dist[maxn]; void dfs(int u) { for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];//倍增DP for(int i=0;i<G[u].size();i++) { Edge &e=G[u][i]; if(e.to==fa[u][0])continue; dep[e.to]=dep[u]+1; dist[e.to]=dist[u]+e.len; fa[e.to][0]=u; dfs(e.to); } } int lca(int x,int y) { if(dep[x]>dep[y])swap(x,y); int f=dep[y]-dep[x]; for(int i=0;(1<<i)<=f;i++)//二进制的思想,总能到达同dep if((1<<i)&f)y=fa[y][i]; if(y==x)return x; for(int i=20;i>=0;i--)//二进制思想,由大到小的减,总能到达1 if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } return fa[x][0]; } int main() { int n,m; scanf("%d%d",&n,&m); int x,y,l; char c; for(int i=0;i<m;i++) { getchar(); scanf("%d %d %d %c",&x,&y,&l,&c); G[x].push_back({y,l}); G[y].push_back({x,l}); } dfs(1); int k; scanf("%d",&k); while(k--) { scanf("%d%d",&x,&y); printf("%d\n",dist[x]+dist[y]-2*dist[lca(x,y)]); } }