출처 : https://www.acmicpc.net/problem/13208

문제에서 그래프가 주어진다.
이걸 또 다른 그래프로 바꿔야 한다.

주어진 그래프에서는 노드가 1, 2, 3, ,,, N까지 있다.

여기서 새로 만들어야 될 그래프는 N^2개의 노드를 가진다.
(1, 1), (1, 2), (1, 3) ,,, (1, N), (2, 1), (2, 2),,,(2, N),,,(N, N)
이것을 다시 1, 2, 3, ,,, N^2로 인덱싱 해준다.
여기서 새로만든 (a, b)노드의 정의는 문제를 그대로 따오자면
조승현13이 a번 노드에 있고, 조승현16이 b번 노드에 있는 '상태'를 나타내는 노드다.

그럼 노드정의는 다 대었으니 노드사이의 간선cost를 구해야 한다.
아무리 생각해도 글로는 좀 힘들것 같아서 그림을 준비해 봄.

아래그림은 입력과 동일
1

현재 조승현13(이하 U), 조승현16(이하 V)가 각각 1번, 4번 노드에 있는 상황
(원 안에 있는 숫자는 노드번호, 원 밖에 있는 숫자는 C_i)
이때 cost는 5 * 100 = 500

여기서 V가 움직인다면.
2

V는 5번 노드에 있고 C_5는 12, 이때 new_cost는 5 * 12 = 60
그러면
(1, 4) (1, 5) 노드 사이의 cost는 max(500, 60) = 500

max(500, 12) = 500 값이여야 U, V가 (1, 4)이던 (1, 5)이던 서로 통신을 할 수 있기 때문
마찬가지로

3

U도 옮겨 가면서 새로 그래프를 만들어 준다.

위의 그림은 (1, 4) 노드와 (2, 4) 노드를 잇는 엣지 cost는 max(500, 100) = 500이 됨

이렇게 새로운 그래프를 구성하고 새로 만들어진 그래프에서 MST를 구성한다.

이후 쿼리 처리는 만들어진 MST에서 (S, E)노드로 부터 (E, S)노드로 가는 경로중 최대값을 구하는 문제로 바뀌게 됨.

이는 LCA를 이용하면 구할 수 있음

으아..
아래는 코드

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
using ll = long long;
struct G
{
	struct edge
	{
		int a, b, f, c;
		bool operator < (const edge& a) const
		{
			return c < a.c;
		}
	};
	vector<edge> el;
	vector<vector<int>>elist, table, olist;
	vector<int> size, parent, chain_num, chain_depth, chain_idx, cindex, dnum, info;
	int ovn, oen, vn, num;
	G(int a, int b) : ovn(a), oen(b), vn(a * a), num(0)
	{
		olist.resize(ovn + 1);
		size.resize(vn + 1, 0);
		parent.resize(vn + 1, 0);
		chain_num.resize(vn + 1, 0);
		chain_depth.resize(vn + 1, 0);
		chain_idx.resize(vn + 1, 0);
		cindex.resize(vn + 1, 0);
		dnum.resize(vn + 1, 0);
		info.resize(ovn + 1);
		fill_table();
		input();
		ex_e();
		elist.resize(vn + 1);
	}
	void input()
	{
		int i, a, b;
		for (i = 1; i <= ovn; i++)
		{
			cin >> info[i];
		}
		for (i = 0; i < oen; i++)
		{
			cin >> a >> b;
			olist[a].push_back(b);
			olist[b].push_back(a);
		}
	}
	void fill_table()
	{
		int i, j, c;
		table.resize(ovn + 1);
		for (i = c = 1; i <= ovn; i++)
		{
			table[i].resize(ovn + 1);
			for (j = 1; j <= ovn; j++)
			{
				table[i][j] = c++;
			}
		}
	}
	void ex_e()
	{
		int u, v, cur, next, d, st, nc, m;
		for (u = 1; u <= ovn; u++)
		{
			for (v = 1; v <= ovn; v++)
			{
				cur = table[u][v];
				st = info[u] * info[v];
				for (auto& nn : olist[u])
				{
					next = table[nn][v];
					nc = info[v] * info[nn];
					m = max(st, nc);
					el.push_back({ cur, next, 0, m });
				}
				for (auto& nn : olist[v])
				{
					next = table[u][nn];
					nc = info[u] * info[nn];
					m = max(st, nc);
					el.push_back({ cur, next, 0, m });
				}
			}
		}
		for (int i = 0; i < ovn; i++)
		{
			olist.clear();
		}
		olist.clear();
	}
	void pb(int a, int b)
	{
		elist[a].push_back(b);
	}
	void build_hld()
	{
		go1(1, 0);
		go2(1, 0, 1, 0);
		for (int i = 0; i <= vn; i++)
		{
			elist[i].clear();
		}
		elist.clear();
		size.clear();
	}
	int go1(int c, int p)
	{
		size[c] = 1;
		parent[c] = p;
		for (auto& nx : elist[c])
		{
			if (nx != p)
			{
				size[c] += go1(nx, c);
			}
		}
		return size[c];
	}
	void go2(int c, int p, int ccn, int ccd)
	{
		int h = -1;
		dnum[c] = ++num;
		chain_num[c] = ccn;
		chain_depth[c] = ccd;
		chain_idx[c] = cindex[ccn]++;
		for (auto& nx : elist[c])
		{
			if (nx != p && (h == -1 || size[nx] > size[h]))
			{
				h = nx;
			}
		}
		if (h != -1)
		{
			go2(h, c, ccn, ccd);
		}
		for (auto& nx : elist[c])
		{
			if (nx != p && nx != h)
			{
				go2(nx, c, nx, ccd + 1);
			}
		}
	}
	int lca(int a, int b)
	{
		while (chain_num[a] != chain_num[b])
		{
			if (chain_depth[a] > chain_depth[b])
			{
				a = parent[chain_num[a]];
			}
			else
			{
				b = parent[chain_num[b]];
			}
		}
		return chain_idx[a] > chain_idx[b] ? b : a;
	}
};
struct UNION_FIND
{
	int vn;
	vector<int>r, p;
	UNION_FIND(int a) :vn(a)
	{
		r.resize(vn + 1, 0);
		p.resize(vn + 1);
		for (int i = 0; i <= vn; i++)
		{
			p[i] = i;
		}
	}
	int find(int x)
	{
		if (x == p[x])
		{
			return x;
		}
		return p[x] = find(p[x]);
	}
	void uni(int x, int y)
	{
		lnk(find(x), find(y));
	}
	void lnk(int x, int y)
	{
		if (r[x] > r[y])
		{
			p[y] = x;
		}
		else
		{
			p[x] = y;
			if (r[x] == r[y])
			{
				r[y]++;
			}
		}
	}
};
struct SEGMENT_TREE
{
	int n, node, s, e, l, r, g;
	vector<int>tree;
	SEGMENT_TREE(int a) : n(a)
	{
		for (node = s = l = r = 1; r - l + 1 < n; l <<= 1, r <<= 1, r |= 1);
		tree.resize(r + 1, 0);
		e = r - l + 1;
		g = l - 1;
	}
	void update(int idx, int val)
	{
		tree[idx] = val;
		idx >>= 1;
		while (idx)
		{
			tree[idx] = max(tree[idx << 1], tree[idx << 1 | 1]);
			idx >>= 1;
		}
	}
	int query(int node, int start, int end, int left, int right)
	{
		int mid;
		if (left > end || right < start)
		{
			return 0;
		}
		if (left <= start && end <= right)
		{
			return tree[node];
		}
		mid = (start + end) >> 1;
		return max(query(node << 1, start, mid, left, right), query(node << 1 | 1, mid + 1, end, left, right));
	}
};
struct SOLUTION
{
	int ovn, en;
	struct G g;
	UNION_FIND uf;
	SEGMENT_TREE seg;
	SOLUTION(int a, int b) : ovn(a), en(b), g(a, b), uf(a * a), seg(a * a)
	{
		make_mst();
		g.build_hld();
		fill_seg();
		proc();
	}
	void make_mst()
	{
		sort(g.el.begin(), g.el.end());
		for (auto& [a, b, f, c] : g.el)
		{
			if (uf.find(a) != uf.find(b))
			{
				f = 1;
				g.pb(a, b);
				g.pb(b, a);
				uf.uni(a, b);
			}
		}
	}
	void fill_seg()
	{
		for (auto& [a, b, f, c] : g.el)
		{
			if (f)
			{
				seg.update(seg.g + g.dnum[g.parent[a] == b ? a : b], c);
			}
		}
		g.el.clear();
	}
	void proc()
	{
		int qn, a, b;
		cin >> qn;
		while (qn--)
		{
			cin >> a >> b;
			cout << query(a, b) << endl;
		}
	}
	int query(int a, int b)
	{
		int l;
		l = g.lca(g.table[a][b], g.table[b][a]);
		return max(hq(l, g.table[a][b]), hq(l, g.table[b][a]));
	}
	int hq(int a, int b)
	{
		int ans = 0;
		while (g.chain_num[a] != g.chain_num[b])
		{
			ans = max(ans, seg.query(seg.node, seg.s, seg.e, g.dnum[g.chain_num[b]], g.dnum[b]));
			b = g.parent[g.chain_num[b]];
		}
		return max(ans, seg.query(seg.node, seg.s, seg.e, g.dnum[a] + 1, g.dnum[b]));
	}
};
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int ovn, en;
	cin >> ovn >> en;
	SOLUTION sol(ovn, en);
	return 0;
}