1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
| #include <iostream> #include <queue> #include <algorithm> #include <cstring>
#define MAXN 500100 #define INF 0x3f3f3f3f
using namespace std;
struct Edge *f[MAXN]; int fa[MAXN][22]; int val[20]; int depth[MAXN]; int n;
struct Edge { int from, to; Edge *next;
Edge(int from = 0, int to = 0): from(from), to(to), next(f[from]) {}
~Edge() { delete next; } };
queue<int> q; void bfs(int s) { memset(depth, INF, sizeof(depth)); depth[0] = 0; depth[s] = 1; q.push(s); while (!q.empty()) { int tmp = q.front(); q.pop(); for (Edge *e = f[tmp]; e; e = e->next) { if (depth[e->to]==INF) { depth[e->to] = depth[tmp] + 1; q.push(e->to);
fa[e->to][0] = tmp; } } } }
void init() { val[0] = 1; for (int i = 1; i<=20; i++) { val[i] = val[i-1] * 2; } for (int j = 1; j<=20; j++) for (int i = 1; i<=n; i++) { fa[i][j] = fa[ fa[i][j-1] ][j-1]; } }
int LCA(int x, int y) { int ans = 0; if (depth[x] < depth[y]) swap(x, y);
for (int i = 20; depth[x]>depth[y]; i--) if (depth[ fa[x][i] ] >= depth[y]) { ans += val[i]; x = fa[x][i]; }
if (x==y) return ans;
for (int i = 20; i>=0; i--) if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; ans += val[i]*2; } ans += 2; return ans; }
int main() { memset(fa, 0, sizeof(fa)); memset(f, 0, sizeof(f));
cin >> n;
for (int i = 1; i<n; i++) { int x, y; cin >> x >> y;
f[x] = new Edge(x, y); f[y] = new Edge(y, x); }
bfs(1); init();
int ans = 0;
int m; cin >> m; int x; cin >> x; for (int i = 1; i<m; i++) { int y; cin >> y; ans += LCA(x, y);
x = y; }
cout << ans << endl; }
|