rt

用的是dfs序+st表求lca

其余思路同第一篇题解

代码：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int ma = 2e5 + 10;
int n,m,q,a0,f[ma],tot;
int dfn[ma],dn,val[ma],fa[ma];
int lg[ma],mi[50][ma];
struct edge{
	int u,v,w;
}a[ma];
struct path{
	int v,w;
};
vector <path> g[ma];
inline void ad(int u,int v,int w)
{
	g[u].push_back({v,w});
	g[v].push_back({u,w});
}
void init()
{
	for(int i = 1; i <= n; i++)
		f[i] = i;
	tot = n;
}
inline int get_root(int k)
{
	if(f[k] == k)return k;
	return f[k] = get_root(f[k]);
}
inline int merge(int x,int y,int w)
{
	x = get_root(x);
	y = get_root(y);
	if(x != y)
	{
		f[y] = x;
		tot--;
		ad(x,y,w);
	}
}
void pre_lg()
{
	for(int i = 2; i <= n; i++)
		lg[i] = lg[i >> 1] + 1;
}
int get(int u,int v)
{
	return dfn[u] < dfn[v] ? u : v;
}
void dfs(int u,int fat)
{
	dfn[u] = ++dn;
	mi[0][dn] = fat;
	fa[u] = fat;
	int len = g[u].size();
	for(int i = 0; i < len; i++)
	{
		int v = g[u][i].v;
		if(!dfn[v])
		{
			val[v] = g[u][i].w;
			dfs(v,u);
		}
	}
}
void st()
{
	for(int i = 1; i <= lg[n]; i++)
		for(int j = 1; j + (1 << i) -1 <= n; j++)
			mi[i][j] = get(mi[i-1][j],mi[i-1][j + (1 << (i-1))]);
}
void pre_lca()
{
	pre_lg();
	dfs(1,-1);
	st();
}
inline int lca(int u,int v)
{
	if(u == v)return u;
	u = dfn[u];
	v = dfn[v];
	if(u > v)
		swap(u,v);
	int d = lg[v-u++];
	return get(mi[d][u],mi[d][v - (1 << d) + 1]);
}
int ans(int u,int v,int l)
{
	int mk = 0;
	while(u != l)
	{
		mk = max(mk,val[u]);
		u = fa[u];
	}
	while(v != l)
	{
		mk = max(mk,val[v]);
		v = fa[v];
	}
	return mk;
}
int main()
{
	ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    init();
    for(int i = 1; i <= m; i++)
    {
    	int k = m-i+1;
    	for(int j = 2; ;j++)
    	{
    		if(j*k > n)break;
    		a[++a0] = {k,j*k,i};
		}
	}
	for(int i = 1; i <= a0; i++)
	{
		if(tot == 1)break;
		merge(a[i].u,a[i].v,a[i].w);
	}
	pre_lca();
	while(q--)
	{
		int u,v;
		cin >> u >> v;
		cout << ans(u,v,lca(u,v)) << '\n';
	}
}