Solution for UVa Online Judge 12655 - Trucks

1. Kruskal to get the MST with the maximum weight. 2. root the tree generated. 3. HeavyLight decomposition on the tree 4. Segment Tree to the heavylight decomposition to get the min edge over a path.

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(v) ((int)v.size())
#define rep(i,m) for(int i=0;i<(int)(m);++i)
#define repe(i,n,m) for(int i=n;i<=(int)(m);++i)
#define rep2(i,n,m) for(int i=n;i<(int)(m);i++)
#define reset(a,b) memset(a,b,sizeof(a))
#define mp make_pair

typedef pair<int, int> pii;

const int oo = (int) 1e9;
const int MAXV = 20001, MAXE = 20001;

struct edge{
 int w, u, v;
 edge(int _u, int _v,int _w):w(_w),u(_u),v(_v){};
 bool operator<(edge e) const{
  if(e.w != w) return w < e.w ;
  if(e.u != u) return u < e.u;
  return v < e.v;
 }
 edge(){u=v=w=0;};
};
edge edges[100001];
vector<vector<pii> > adjj;
int parent2[20001];
int getParent(int n){
 if(parent2[n] == -1) return n;
 return parent2[n] = getParent(parent2[n]);
}
bool Union(int a, int b){
 int pa = getParent(a);
 int pb = getParent(b);
 if(pa == pb) return false;
 parent2[pa] = pb;
 return true;
}
int m, s;
void kruskal(){
 reset(parent2,-1);
 rep(i,m){
  int u = edges[i].u, v = edges[i].v, w = -edges[i].w;
  if(Union(u,v)){
   adjj[u].pb(mp(v,w));
   adjj[v].pb(mp(u,w));
  }
 }
}

int head[MAXV], nxt[MAXE], to[MAXE], from[MAXE], cost[MAXE];
int parent[MAXV], siz[MAXV], lvl[MAXV], hvyChild[MAXV], hvyRoot[MAXV],
  hvyCost[MAXV];
bool isHeavy[MAXE];
int last;
int t, n;
void init() {
 reset(head, -1);
 reset(parent, -1);
 last = 0;
}
void addEdge(int f, int t, int c) {
 isHeavy[last] = false;
 parent[t] = last;
 from[last] = f;
 to[last] = t;
 cost[last] = c;
 nxt[last] = head[f];
 head[f] = last++;
}
int dfs(int root, int depth) {
 siz[root] = 1;
 lvl[root] = depth;
 hvyChild[root] = -1;
 hvyRoot[root] = root;
 for (int i = head[root]; i != -1; i = nxt[i])
  siz[root] += dfs(to[i], depth + 1);
 for (int i = head[root]; i != -1; i = nxt[i])
  if (siz[to[i]] >= (siz[root] + 1) / 2) {
   isHeavy[i] = true;
   hvyChild[root] = i;
   hvyCost[root] = cost[i];
  }
 return siz[root];
}
void heavyLight(int root = 0) {
 dfs(root, 0);
 for (int i = 0; i < last; i++) {
  if (!isHeavy[i])
   continue;
  int f = from[i];
  if (parent[f] == -1 || !isHeavy[parent[f]])
   for (int k = i; k != -1; k = hvyChild[to[k]])
    hvyRoot[to[k]] = f;
 }
}
int LCA(int a, int b) {
 while (hvyRoot[a] != hvyRoot[b])
  if (lvl[hvyRoot[a]] > lvl[hvyRoot[b]])
   a = from[parent[hvyRoot[a]]];
  else
   b = from[parent[hvyRoot[b]]];
 if (lvl[a] < lvl[b])
  return a;
 return b;
}
//vector<vector<pii> > adjj;
void root(int u, int prv = -1) {
 rep(i,sz(adjj[u]))
 {
  int v = adjj[u][i].first, c = adjj[u][i].second;
  if (v == prv)
   continue;
  addEdge(u, v, c);
  root(v, u);
 }
}

int tree[MAXV * 4];
int dic[MAXV], cur;

void update(int l, int r, int n, int val, int idx = 1) {
 if (n > r || n < l)
  return;
 if (n == r && n == l) {
  tree[idx] = val;
  return;
 }
 int mid = l + (r - l) / 2, li = idx * 2, ri = li + 1;
 update(l, mid, n, val, li);
 update(mid + 1, r, n, val, ri);
 tree[idx] = min(tree[li], tree[ri]);
}
int query(int l, int r, int st, int en, int idx = 1) {
 if (r < st || l > en)
  return oo;
 if (st <= l && en >= r)
  return tree[idx];
 int mid = l + (r - l) / 2, li = idx * 2, ri = li + 1;
 return min(query(l, mid, st, en, li), query(mid + 1, r, st, en, ri));
}

void buildHeavyLightSegTree(int u, int c = -1) {
 if (c != -1)
  update(0, n, cur, c);
 dic[u] = cur++;
 if (hvyChild[u] != -1)
  buildHeavyLightSegTree(to[hvyChild[u]], hvyCost[u]);
 for (int i = head[u]; i != -1; i = nxt[i])
  if (to[i] != to[hvyChild[u]])
   buildHeavyLightSegTree(to[i], cost[i]);
}
int _queryHeavyLight(int u, int lca) {
 if (lca == u)
  return oo;
 if (lvl[lca] >= lvl[hvyRoot[u]])
  return query(0, n, dic[to[hvyChild[lca]]], dic[u]);
 if (hvyRoot[u] != u)
  return min(query(0, n, dic[hvyRoot[u]], dic[u]),
    _queryHeavyLight(from[parent[hvyRoot[u]]], lca));
 return min(cost[parent[u]], _queryHeavyLight(from[parent[u]], lca));
}
int queryHeavyLight(int u, int v) {
 int lca = LCA(u, v);
 return min(_queryHeavyLight(u, lca), _queryHeavyLight(v, lca));
}
void updateHeavyLight(int u, int val) {
 update(0, n, dic[u], val);
}
int main() {
 ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
 freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
#endif
 while(cin >> n >> m >> s){
  int u,v,w;
  rep(i,m){
   cin >> u >> v >> w;
   u--,v--;
   edges[i] = edge(u,v,-w);
  }
  sort(edges,edges+m);
  adjj.clear();
  adjj.resize(n);
  kruskal();
  init();
  int a, b;

  root(0);

  //  debugx(heavyLight);
  heavyLight(0);
  reset(tree, 0);
  reset(dic, -1);
  cur = 0;
  //  debugx(buildHeavyLightSegTree);
  buildHeavyLightSegTree(0);
//  string s;
  rep(i,s){
   cin >> a >> b;
   a--,b--;
   cout << queryHeavyLight(a,b)<<endl;
  }
 }
 return 0;
}