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);
}