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

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 15005;
const int inf = 1e9;

int de[maxn];
int son[maxn];
int fa[maxn];
int top[maxn];
int dfn[maxn];
int size[maxn];
int in[maxn];
int out[maxn];
int v[maxn];
int n, m, k;

class segment_tree {
private:
	struct node {
		int l, r;
		int v;
		node() {}
		node(int l_, int r_, int v_) { l = l_, r = r_, v = v_; }
	}ns[maxn<<2];
public:
	void build(int i, int l, int r) {
		if(l == r) {
			ns[i] = node(l, r, v[out[l]]);
			return;
		}
		build(i << 1, l, (l+r)>>1);
		build(i << 1 | 1,((l+r) >> 1) + 1, r);
		ns[i] = node(l, r, max(ns[i << 1].v, ns[i << 1 | 1].v));
	}
	
	int query_max(int i, int l, int r) {
		if(ns[i].l == l && ns[i].r == r) return ns[i].v;
		else if(r <= ns[i << 1].r) return query_max(i << 1, l, r);
		else if(l >= ns[i << 1 | 1].l) return query_max(i << 1 | 1, l, r);
		else if(l <= ns[i << 1].r && r>=ns[i << 1 | 1].l)
			return max(query_max(i << 1, l, ns[i << 1].r),
					   query_max(i << 1 | 1, ns[i << 1 | 1].l, r));
	}
}st;

class cut_tree{
private:
	struct edge {
		int to, ne, v;
		edge() {}
		edge(int to_, int ne_, int v_) { to = to_, ne = ne_, v = v_; }
	}e[maxn<<1];
	int head[maxn], tot;
	
	int cnt;
	
	void dfs1(int now, int deep, int f) {
		de[now] = deep;
		fa[now] = f;
		size[now] = 1;
		for(int i = head[now]; i; i = e[i].ne) {
			int to = e[i].to;
			if(to == f) continue;
			v[to] = e[i].v;
			dfs1(to, deep+1, now);
			size[now] += size[to];
			if(!son[now] || size[to] > size[son[now]]) {
				son[now] = to;
			}
		}
	}
	
	void dfs2(int now, int t) {
		in[now] = ++cnt;
		out[cnt] = now;
		top[now] = t;
		if(son[now]) dfs2(son[now], t);
		
		for(int i = head[now]; i; i = e[i].ne) {
			int to = e[i].to;
			if(to == fa[now] || to == son[now]) continue;
			dfs2(to, to);
		}
	}
	
public:
	void add_edge(int fr, int to, int v) {
		e[++tot] = edge(to, head[fr], v); head[fr] = tot;
		e[++tot] = edge(fr, head[to], v); head[to] = tot;
	}
	
	void build() {
		dfs1(1, 1, 0);
		dfs2(1, 1);
		v[1] = -inf;
		st.build(1, 1, cnt);
	}
	
	int query_max(int fr, int to) {
		int ans = -inf;
		int f1 = top[fr], f2 = top[to];
		while(f1 != f2) {
			if(de[f1] < de[f2]) {
				swap(f1, f2);
				swap(fr, to);
			}
			ans = max(ans, st.query_max(1, in[f1], in[fr]));
			fr = fa[f1], f1 = top[fr];
		}
		if(fr != to) ans = max(ans, de[fr] < de[to] ?
				  st.query_max(1, in[son[fr]], in[to]):
				  st.query_max(1, in[son[to]], in[fr]));
		return ans;
	}
	
	void outer(int now) {
		printf("now = %d fa = %d v = %d\n", now, fa[now], v[now]);
	}
	
	void d(int now) {
		outer(now);
		for(int i = head[now]; i; i = e[i].ne) {
			if(e[i].to == fa[now]) continue;
			d(e[i].to);
		}
	}
	void test() {
		d(1);
	}
	
}ct;

class union_set {
private:
	int r[maxn];
public:
	union_set() {
		for(int i = 1; i <= n; i++) { r[i] = i; }
	} 
	int find_fa(int a) {
		return r[a] = r[a] == a ? a : find_fa(r[a]);
	}
	void union_fa(int a, int b) {
		if(a == b) return;
		int faa = find_fa(a), fab = find_fa(b); 
		r[faa] = fab;
	}
	bool same(int a, int b) {
		int faa = find_fa(a), fab = find_fa(b); 
		return faa == fab;
	}
};

class min_tree {
private:
	struct edge {
		int fr, to, ne, v;
		edge() {}
		edge(int fr_, int to_, int ne_, int v_) { fr = fr_, to = to_, ne = ne_, v = v_; }
		bool operator < (const edge& b) const {
			return v <= b.v;
		}
	}e[maxn*2];	
	int head[maxn], tot;
public:
	void add_edge(int fr, int to, int v) {
		e[++tot] = edge(fr, to, head[fr], v); head[fr] = tot;
	}
	void make_tree() {
		union_set us;
		sort(e+1, e+m+1);
		int cnt = 0;
		for(int i = 1; i <= m; i++) {
			if(us.same(e[i].fr, e[i].to)) continue;
			us.union_fa(e[i].fr, e[i].to);
			ct.add_edge(e[i].fr, e[i].to, e[i].v);
			cnt++;
			if(cnt == n) break;
		}
	}
}mt;

void read() {
	scanf("%d %d %d", &n, &m, &k);
	int a, b, c;
	for(int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		mt.add_edge(a, b, c);
	}
} 
void solve() {
	mt.make_tree();
	ct.build();
//	ct.test();
	int a, b;
	for(int i = 1; i <= k; i++) {
		scanf("%d %d", &a, &b);
		printf("%d\n", ct.query_max(a, b));
	}
}

int main() {
	freopen("heatwave.in", "r", stdin);
	freopen("heatwave.out", "w", stdout);
	read();
	solve();
	return 0;
}