HDU 2586 How far away ？【LCA】

題目鏈接：

http://acm.hdu.edu.cn/showproblem.php?pid=2586

題意：

無向圖，給定邊及邊權重，任意兩點之間都有一條唯一的道路，道路上每個點只能出現一次。給定詢問，求詢問的結點之間的距離。

分析：

路上每個點只能出現一次~可以轉化成有根樹，問題也即為求最近公共祖先問題~~
這里每條邊加上了距離，求出lca后，用u、v的距離根的距離和減去2倍的根到最近公共祖先的距離即可~

代碼：

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define fuck cout<<"fuck"<<endl;
const int maxn = 40005, maxq = 205;
typedef pair<int, int>p;
vector<p>G[maxn];
#define fi first
#define se second
int pa[maxn];
bool vis[maxn];
bool in[maxn];
int ance[maxn];
int dist[maxn];
int n, tot;
int head[maxn];
int ans[maxn];
struct Query{int to, next, index;};
Query query[maxq * 2];
void add_query(int u, int v, int index)
{query[tot].to = v;query[tot].index = index;query[tot].next = head[u];head[u] = tot++;query[tot].to = u;query[tot].index = index;query[tot].next = head[v];head[v] = tot++;
}
int _find(int x)
{if(pa[x] != x) return pa[x] = _find(pa[x]);return x;
}
void unite(int x, int y)
{int rx = _find(x), ry = _find(y);if(rx == ry) return;pa[rx] = ry;
}
void init()
{tot = 0;for(int i = 1; i <= n; i++){G[i].clear();pa[i] = i;}mem(ance, 0);mem(vis, false);mem(head, -1);mem(dist, 0);mem(in, false);mem(ans, 0);
}
void LCA(int u)
{ance[u] = u;vis[u] = true;for(int i = 0; i < G[u].size(); i++){int v = G[u][i].fi;if(vis[v]) continue;dist[v] = dist[u] + G[u][i].se;LCA(v);unite(u, v);ance[_find(u)] = u;}for(int i = head[u]; i != -1; i = query[i].next){int v = query[i].to;if(vis[v])  ans[query[i].index] = dist[u] + dist[v] - 2 * dist[ance[_find(u)]];}
}
int main(void)
{int u, v, k;int a, b, c;int Q;int T;scanf("%d", &T);while(T--){init();scanf("%d%d", &n, &Q);for(int i = 0; i < n - 1; i++){scanf("%d%d%d",&a, &b, &c);G[a].push_back(p(b, c));G[b].push_back(p(a, c));}for(int i = 0; i < Q; i++){scanf("%d%d",&u,&v);add_query(u, v, i);}dist[1] = 0;LCA(1);for(int i = 0; i <Q; i++){printf("%d\n", ans[i]);}}return 0;
}