Ｔａｒｊａｎ：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; const int MAX = 40005; int n, m; struct Edge { int lca, v, to, next, st; } edge1[MAX * 2], edge2[MAX * 2]; int k = 0; int head1[MAX]; void add1(int a, int b, int c){ edge1[k].to = b; edge1[k].next = head1[a]; edge1[k].v = c; head1[a] = k++; } int head2[MAX]; void add2(int a, int b){ edge2[k].st = a; edge2[k].to = b; edge2[k].next = head2[a]; head2[a] = k++; } int par[MAX]; int Find(int x){ if(x == par[x]){ return x; } return par[x] = Find(par[x]); } void unit(int x, int y){ x = Find(x); y = Find(y); if(x == y){ return ; } par[y] = x; } int dis[MAX]; int vis[MAX]; void Tarjan(int rt){ vis[rt] = 1; for(int i = head1[rt]; i != -1; i = edge1[i].next){ int to = edge1[i].to; if(vis[to] == 0){ dis[to] = dis[rt] + edge1[i].v; Tarjan(to); unit(rt, to); } } for(int i = head2[rt]; i != -1; i = edge2[i].next){ int to = edge2[i].to; if(vis[to]){ edge2[i].lca = Find(to); edge2[i ^ 1].lca = Find(to); } } } int main() { int t; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++){ head2[i] = head1[i] = -1; par[i] = i; vis[i] = 0; dis[i] = 0; } k = 0; for(int i = 1; i < n; i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); add1(a, b, c); add1(b, a, c); } k = 0; for(int i = 0; i < m; i++){ int a, b; scanf("%d%d", &a, &b); add2(a, b); add2(b, a); } Tarjan(1); for(int i = 0; i < k; i += 2){ int st = edge2[i].st; int to = edge2[i].to; int lca = edge2[i].lca; int ans = dis[st] + dis[to] - 2 * dis[lca]; printf("%d\n", ans); } } return 0; }
倍增：
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <queue> #include <cmath> #include <map> using namespace std; const int MAX=4e4 + 50; int n, m; int depth[MAX]; int fa[MAX][60]; int in[MAX]; struct Edge { int to; int v; int next; } edge[2 * MAX]; int head[MAX]; int k = 0; void add(int a, int b, int c){ edge[k].to = b; edge[k].next = head[a]; edge[k].v = c; head[a] = k++; } int dis[MAX]; void dfs(int u, int pre, int d){ fa[u][0] = pre; depth[u] = d; for(int i = head[u]; i != -1; i = edge[i].next){ int to = edge[i].to; if(to != pre){ dis[to] = dis[u] + edge[i].v; dfs(to, u, d + 1); } } } void init(int root){ dfs(root, -1, 0); for(int j = 0; (1 << (j + 1)) < n; j++){ for(int i = 1; i <= n; i++){ if(fa[i][j] < 0){ fa[i][j + 1] = -1; } else{ fa[i][j + 1] = fa[fa[i][j]][j]; } } } } int LCA(int u, int v){ if(depth[u] > depth[v]){ swap(u, v); } int temp = depth[v] - depth[u]; for(int i = 0; (1 << i) <= temp; i++){ if((1 << i) & temp){ v = fa[v][i]; } } if(v == u){ return u; } int k = log2(n); for(int i = k; i >= 0; i--){ if(fa[u][i] != fa[v][i]){ u = fa[u][i]; v = fa[v][i]; } } return fa[u][0]; } int main() { int t; scanf("%d", &t); while(t--){ k = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++){ in[i] = 0; fa[i][0] = 0; head[i] = -1; dis[i] = 0; } for(int i = 1; i < n; i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); add(b, a, c); } dfs(1, -1, 0); init(1); for(int i = 0; i < m; i++){ int a, b; scanf("%d%d", &a, &b); int lca = LCA(a, b); printf("%d\n", dis[a] + dis[b] - 2 * dis[lca]); } } return 0; };ＲＭＱ
#include <iostream> #include <cstdio> #include <string.h> #include <vector> #include <algorithm> #include <iostream> #include <map> #include <queue> #include <cmath> using namespace std; #define LL long long const int MAX = 4e4 + 50; struct Edge { int to; int next; int v; } edge[MAX * 2]; int n, tot, m; int id[MAX * 2], depth[2 * MAX], head[MAX * 2]; int ss[MAX], dp[2 * MAX][60], in[MAX]; int k = 0; void add(int a, int b, int c){ edge[k].to = b; edge[k].next = head[a]; edge[k].v = c; head[a] = k++; } int dis[MAX]; void dfs(int u, int pre, int d){ id[++tot] = u; ss[u] = tot; depth[tot] = d; for(int i = head[u]; i != -1; i = edge[i].next){ int to = edge[i].to; if(to == pre){ continue; } dis[to] = dis[u] + edge[i].v; dfs(to, u, d + 1); id[++tot] = u; depth[tot] = d; } } void ST(){ int nn = 2 * n - 1; int kk = log2(nn); for(int i = 1; i <= nn; i++){ dp[i][0] = i; } for(int j = 1; j <= kk; j++){ for(int i = 1; i + (1 << j) - 1 <= nn; i++){ int a = dp[i][j - 1]; int b = dp[i + (1 << (j - 1))][j - 1]; if(depth[a] < depth[b]){ dp[i][j] = a; } else{ dp[i][j] = b; } } } } int RMQ(int l, int r){ int kk = log2(r - l + 1); int a = dp[l][kk]; int b = dp[r - (1 << kk) + 1][kk]; if(depth[a] < depth[b]){ return a; } else{ return b; } } int LCA(int x, int y){ int l = ss[x]; int r = ss[y]; if(l > r){ swap(l, r); } return id[RMQ(l, r)]; } int main() { int t; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &m); k = 0; tot = 0; for(int i = 1; i <= n; i++){ head[i] = -1; dis[i] = 0; } for(int i = 1; i < n; i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); add(b, a, c); } dfs(1, -1, 0); ST(); for(int i = 0; i < m; i++){ int a, b; scanf("%d%d", &a, &b); int lca = LCA(a, b); printf("%d\n", dis[a] + dis[b] - 2 * dis[lca]); } } return 0; }
