记录编号	252142	评测结果	AAAAAAAAAA
题目名称	图的询问	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.510 s
提交时间	2016-04-19 16:19:17	内存使用	1.56 MiB

//KZNS
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
//
ifstream fin ("heatwave.in");
ofstream fout ("heatwave.out");
typedef pair<int, int> pr;
typedef pair<int, pr> poi;
const int Nmax = 15003;
class pp {
public:
	int l, r, mx;
}tr[64000];
//
int N, M, K;
vector<pr> gp[Nmax];
vector<poi> ls;
int fa[Nmax];
int cts[Nmax] = {0};
int ff[Nmax] = {0};
int ddp[Nmax] = {0};
int hc[Nmax] = {0};
int dtm[Nmax] = {0}, tmu = 1;
int dtp[Nmax] = {0};
int pv[Nmax] = {0};
int vtp[Nmax] = {0};
//
inline void fir() {
	fin >> N >> M >> K;
	int a, b, c;
	for (int i = 0; i < M; i++) {
		fin >> a >> b >> c;
		ls.push_back(make_pair(c, make_pair(a, b)));
	}
}
inline void ffa() {
	for (int i = 0; i <= N; i++)
		fa[i] = i;
}
int FA(int x) {
	if (fa[x] != x)
		fa[x] = FA(fa[x]);
	return fa[x];
}
inline void mnt() {
	for (int i = 0; i < ls.size(); i++) {
		pr u = ls[i].second;
		if (FA(u.first) != FA(u.second)) {
			fa[fa[u.first]] = fa[u.second];
			gp[u.first].push_back(make_pair(u.second, ls[i].first));
			gp[u.second].push_back(make_pair(u.first, ls[i].first));
		}
	}
}
void DFS1(int x) {
	ddp[x] = ddp[ff[x]] + 1;
	cts[x] = 1;
	for (int i = 0; i < gp[x].size(); i++) {
		if (!cts[gp[x][i].first]) {
			int t = gp[x][i].first;
			ff[t] = x;
			pv[t] = gp[x][i].second;
			DFS1(t);
			cts[x] += cts[t];
			if (cts[t] > cts[hc[x]])
				hc[x] = t;
		}
	}
}
void DFS2(int x, int tp) {
	dtp[x] = tp;
	dtm[x] = tmu++;
	if (hc[x]) {
		DFS2(hc[x], tp);
	}
	for (int i = 0; i < gp[x].size(); i++) {
		if (!dtm[gp[x][i].first]) {
			int t = gp[x][i].first;
			DFS2(t, t);
		}
	}
}
inline void VTP() {
	for (int i = 1; i <= N; i++)
		vtp[dtm[i]] = pv[i];
}
void maketree(int x, int l, int r) {
	pp &u = tr[x];
	u.l = l;
	u.r = r;
	if (l < r) {
		maketree(x<<1, l, l+r>>1);
		maketree(x<<1^1, (l+r>>1)+1, r);
		u.mx = max(tr[x<<1].mx, tr[x<<1^1].mx);
	}
	else {
		u.mx = vtp[r];
	}
	
}
int Qin(int x, int l, int r) {
	pp &u = tr[x];
	if (l <= u.l && u.r <= r)
		return u.mx;
	else {
		int u = -0x7fffffff;
		if (l <= tr[x<<1].r)
			u = max(u, Qin(x<<1, l, r));
		if (tr[x<<1^1].l <= r)
			u = max(u, Qin(x<<1^1, l, r));
		return u;
	}
}
//
int main() {
	fir();
	sort(ls.begin(), ls.end());
	ffa();
	mnt();
	DFS1(1);
	DFS2(1, 1);
	VTP();
	maketree(1, 1, N);
	int a, b;
	for (int i = 0; i < K; i++) {
		fin >> a >> b;
		int u = -0x7fffffff;
		while (a!=b) {
			if (dtp[a] == dtp[b]) {
				u = max(u, Qin(1, min(dtm[a], dtm[b])+1, max(dtm[a], dtm[b])));
				a = b;
			}
			else {
				if (ddp[dtp[a]] > ddp[dtp[b]]) {
					if (dtp[a] == a) {
						u = max(u, Qin(1, dtm[a], dtm[a]));
						a = ff[a];
					}
					else {
						u = max(u, Qin(1, dtm[dtp[a]]+1, dtm[a]));
						a = dtp[a];
					}
				}
				else {
					if (dtp[b] == b) {
						u = max(u, Qin(1, dtm[b], dtm[b]));
						b = ff[b];
					}
					else {
						u = max(u, Qin(1, dtm[dtp[b]]+1, dtm[b]));
						b = dtp[b];
					}
				}
			}
		}
		fout << u << endl;
	}
	return 0;
}
//UWBH