PKU 1986 - Distance Queries
問題文 : Distance Queries
解法 :
Highwayの, 渋滞情報変更が無いだけのSimple LCAの問題.(その前に最小全域木化しなければならないが)
Euler-Tour をしたが, これはDoubling でも普通に解けそう.
全体でO((N+K)logN) くらいの計算量となる. 何も見ないで書けるようになっているのでとても良い.
コード :
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cstdlib> #define MAX_N (40000) using namespace std; typedef pair<int, int> P; struct edge { int from, to, cost; edge(int from, int to, int cost) : from(from), to(to), cost(cost){} edge(){} }; struct Edge { int id, to, cost; Edge(int id, int to, int cost) : id(id), to(to), cost(cost){} Edge(){} }; bool operator < (const edge &a, const edge &b) { return (a.cost < b.cost); } vector<edge> v; vector<Edge> G[MAX_N]; int par[MAX_N]; void init(int n) { for (int i = 0; i < n; i++) par[i] = i; } int find(int x) { if (x == par[x]) return (x); return (par[x] = find(par[x])); } bool same(int x, int y) { return (find(x) == find(y)); } void merge(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rand() & 1) par[y] = x; else par[x] = y; } int treeV[MAX_N * 2 - 1]; int treeE[(MAX_N - 1) * 2]; int id[MAX_N]; int depth[2 * MAX_N - 1]; int bit[MAX_N * 2]; void add(int pos, int val) { while (pos < MAX_N * 2){ bit[pos] += val; pos += pos & -pos; } } int sum(int pos) { int ret = 0; while (pos){ ret += bit[pos]; pos &= (pos - 1); } return (ret); } void preDFS(int v, int p, int d, int &k) { id[v] = k; depth[k] = d; treeV[k++] = v; for (int i = 0; i < G[v].size(); i++){ Edge e = G[v][i]; if (e.to != p){ treeE[2 * e.id] = k; add(k, e.cost); preDFS(e.to, v, d + 1, k); treeV[k] = v; depth[k++] = d; treeE[2 * e.id + 1] = k; add(k, -e.cost); } } } P seg[1 << 20]; int size; void initRMQ(int n) { size = 1; while (size < n) size *= 2; for (int i = 0; i < 2 * size - 1; i++){ seg[i].first = 999999; seg[i].second = -1; } for (int i = 0; i < n; i++){ int k = i + size - 1; seg[k].first = depth[i]; seg[k].second = i; while (k){ k = (k - 1) / 2; seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]); } } } P getMin(int a, int b, int k = 0, int l = 0, int r = size) { if (b <= l || r <= a){ return (P(999999, -1)); } if (a <= l && r <= b){ return (seg[k]); } P left = getMin(a, b, k * 2 + 1, l, (l + r) / 2); P right = getMin(a, b, k * 2 + 2, (l + r) / 2, r); return (min(left, right)); } void initTree(int root, int n) { int k = 0; preDFS(root, -1, 0, k); initRMQ(2 * n - 1); } int getLCA(int u, int v) { if (u > v) swap(u, v); return (treeV[getMin(u, v + 1).second]); } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++){ int from, to, cost; char dummy[2]; scanf("%d %d %d %s", &from, &to, &cost, dummy); v.push_back(edge(from - 1, to - 1, cost)); } int idx = 0; init(n); sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++){ if (!same(v[i].from, v[i].to)){ merge(v[i].from, v[i].to); G[v[i].from].push_back(Edge(idx, v[i].to, v[i].cost)); G[v[i].to].push_back(Edge(idx, v[i].from, v[i].cost)); idx++; } } initTree(abs(rand()) % n, n); int Q; scanf("%d", &Q); for (int i = 0; i < Q; i++){ int s, t; scanf("%d %d", &s, &t); int p = getLCA(id[--s], id[--t]); printf("%d\n", sum(id[s]) + sum(id[t]) - 2 * sum(id[p])); } return (0); }