HDU - 2586 How far away （（LCA最近公共祖先））树---LCA

LCA入门问题，以后总结~~~

#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,a,n) for (int i=a; i=a; i--) #define oo cout<<"!!!"<q; q.push(1); d[1] = 1; while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = Next[i]) { int y = ver[i]; if(d[y])continue; d[y] = d[x] + 1; dist[y] = dist[x] + edge[i]; f[y][0] = x; for(int j = 1; j<=t; j++) f[y][j] = f[f[y][j-1]][j-1]; q.push(y); } } }int lca(int x,int y) { if(d[x]>d[y])swap(x,y); for(int i = t; i>=0; i--) if(d[f[y][i]] >= d[x]) y = f[y][i]; if(x == y)return x; for(int i = t; i>=0; i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i]; return f[x][0]; }int main() { int T; cin>>T; while(T--) { int n,m; cin>>n>>m; t = (int)(log(n)/log(2))+1; rep(i,1,n+1)head[i] = d[i] = dist[t] = 0; tot = 0; rep(i,1,n) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } bfs(); rep(i,1,m+1) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",dist[x]+dist[y]-2*dist[lca(x,y)]); } } }

【HDU - 2586 How far away （（LCA最近公共祖先））】