HDU 2586 How far away ？——lca

假设dis【i】为i到根节点的距离，那么u和v之间的距离为dis【u】 + dis【v】 - 2 * dis【lca（u，v）】

#include #include #include #include #include using namespace std;typedef pair P;const int maxn = 4 * 1e4 + 10;int n, m;vector

G[maxn];vector

link[maxn];int ans[500];int par[maxn];bool vis[maxn];struct Data { int u, v;}data[500];int dis[maxn];//节点i到根节点1的距离int query(int x) { return par[x] == x ? x : par[x] = query(par[x]);}void merge(int x, int y) { x = query(x); y = query(y); if (x != y) par[y] = x;}void lca(int u) { vis[u] = true; for (unsigned int i = 0; i < G[u].size(); i++) { int v = G[u][i].first, d = G[u][i].second; if (!vis[v]) { dis[v] = dis[u] + d; lca(v); merge(u, v); } } for (unsigned int i = 0; i < link[u].size(); i++) { int v = link[u][i].first, id = link[u][i].second; if (vis[v]) ans[id] = query(v); }}void solve() { for (int i = 1; i <= m; i++) { int u = data[i].u, v = data[i].v; ans[i] = dis[u] + dis[v] - 2 * dis[ans[i]]; }}int main() { int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d %d", &n, &m); for (int i = 0; i <= n; i++) G[i].clear(), link[i].clear(), par[i] = i, vis[i] = false, dis[i] = 0; for (int i = 1; i <= n - 1; i++) { int u, v, dis; scanf("%d %d %d", &u, &v, &dis); G[u].push_back(make_pair(v, dis)); G[v].push_back(make_pair(u, dis)); } for (int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); data[i].u = u, data[i].v = v; link[u].push_back(make_pair(v, i)); link[v].push_back(make_pair(u, i)); } lca(1); solve(); for (int i = 1; i <= m; i++) { printf("%d\n", ans[i]); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。