poj1986
LCA模板题
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ms(i, j) memset(i, j, sizeof i) using namespace std; const int MAXN = 40000 + 5, logs = 22; struct edge { int x, y, v; }ed[MAXN*2]; int en; int n, m, deep[MAXN], far[MAXN], pre[MAXN][logs+1]; vector<int> G[MAXN]; void dfs(int x, int p) { pre[x][0] = p; for (int i=1;i<=logs;i++) pre[x][i] = pre[pre[x][i-1]][i-1]; for (int i=0;i<G[x].size();i++) { int v = ed[G[x][i]].y; if (v!=p) { deep[v] = deep[x] + 1; far[v] = far[x] + ed[G[x][i]].v; dfs(v, x); } } } int lca(int a, int b) { if (deep[a]>deep[b]) swap(a,b); for (int i=logs;i>=0;i--) if (deep[pre[b][i]]>=deep[a]) b = pre[b][i]; if (a==b) return a; for (int i=logs;i>=0;i--) if (pre[a][i]!=pre[b][i]) a = pre[a][i], b = pre[b][i]; return pre[a][0]; } void addedge(int x, int y, int v) { en++, ed[en].x = x, ed[en].y = y, ed[en].v = v, G[x].push_back(en); en++, ed[en].x = y, ed[en].y = x, ed[en].v = v, G[y].push_back(en); } void init() { for (int i=1;i<=n;i++) { G[i].clear(); deep[i] = far[i] = 0; for (int j=0;j<=logs;j++) pre[i][j] = 0; } en = 0; for (int i=1;i<=m;i++) { int x, y, v; char str[20]; scanf("%d%d%d%s", &x, &y ,&v, str); addedge(x, y, v); } } void solve() { dfs(1, 0); int q; scanf("%d", &q); for (int i=1;i<=q;i++) { int x, y; scanf("%d%d", &x, &y); printf("%d\n", far[x]+far[y]-2*far[lca(x,y)]); } } int main() { while (scanf("%d%d", &n, &m)==2) { init(); solve(); } return 0; }