【luogu P2245 星际导航】 题解

题目链接：https://www.luogu.org/problemnew/show/P2245

= 货车运输

被逼着写过mst+lca

后来成了mst+树剖

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 100010;

int n, m, q, node[maxn], f[maxn];

struct mst{

	int u, v, w;

}ee[maxn*3];

struct edge{

	int next, to, len;

}e[maxn*3];

int head[maxn], cnt;

void add(int u, int v, int w)

{

	e[++cnt].len = w; e[cnt].next = head[u]; e[cnt].to = v; head[u] = cnt;

	e[++cnt].len = w; e[cnt].next = head[v]; e[cnt].to = u; head[v] = cnt;

}

//-----Kruskal-----

bool cmp(mst a, mst b)

{

	return a.w > b.w;

}

int find(int x)

{

	return f[x] == x ? x : f[x] = find(f[x]);

}

void Kruskal()

{

	sort(ee+1, ee+1+m, cmp);

	for(int i = 1; i <= m; i++)

	{

		if(find(ee[i].u) == find(ee[i].v)) continue;

		add(ee[i].v, ee[i].u, ee[i].w);

		f[find(ee[i].v)] = f[find(ee[i].u)];

	}

}

//----------------

int top[maxn], size[maxn], son[maxn], fa[maxn], seg[maxn], rev[maxn], deep[maxn], num = -1;

void dfs(int u, int f)

{

	fa[u] = f;

	for(int i = head[u]; i != -1; i = e[i].next)

	{

		if(e[i].to == fa[u]) continue;

		node[e[i].to] = e[i].len;

		dfs(e[i].to, u);

	}

}

void dfs1(int u)

{

	int maxson = -1;

	deep[u] = deep[fa[u]]+1;

	size[u] = 1;

	son[u] = n+1;

	for(int i = head[u]; i != -1; i = e[i].next)

	{

		int v = e[i].to;

		if(v == fa[u]) continue;

		dfs1(v);

		size[u] += size[v];

		if(maxson < size[v]) maxson = size[v], son[u] = v;

	}

}

void dfs2(int u, int t)

{

	top[u] = t;

	num++;

	seg[u] = num;

	rev[num] = u;

	if(son[u] != n+1) dfs2(son[u], t);

	for(int i = head[u]; i != -1; i = e[i].next)

	{

		if(e[i].to == fa[u] || e[i].to == son[u]) continue;

		dfs2(e[i].to, e[i].to);

	}

}

//-------------------

class Segment_Tree{

	#define lson l, mid, rt<<1

	#define rson mid+1, r, rt<<1|1

	public:

		int tree[maxn<<2];

		void build(int l, int r, int rt)

		{

			if(l == r)

			{

				tree[rt] = node[rev[l]];

				return;

			}

			int mid = (l + r) >> 1;

			build(lson);

			build(rson);

			PushUP(rt);

		}

		int query(int left, int right, int l, int r, int rt)

		{

			int res = 0x7fffffff;

			if(left <= l && r <= right) return tree[rt];

			int mid = (l + r) >> 1;

			if(left <= mid) res = min(res, query(left, right, lson));

			if(right > mid) res = min(res, query(left, right, rson));

			return res;

		}

		int Qrange(int x, int y)

		{

			int ret = 0x7fffffff;

			while(top[x] != top[y])

			{

				if(deep[top[x]] < deep[top[y]]) swap(x, y);

				ret = min(ret, query(seg[top[x]], seg[x], 1, n, 1));

				x = fa[top[x]];

			}

			if(deep[x] > deep[y]) swap(x, y);

			ret = min(ret, query(seg[x]+1, seg[y], 1, n, 1));

			return ret;

		}

	private:

		void PushUP(int rt)

		{

			tree[rt] = min(tree[rt<<1], tree[rt<<1|1]);

		}

}T;

int main()

{

	ios::sync_with_stdio(false);

	memset(head, -1, sizeof(head));

	cin>>n>>m;

	for(int i = 1; i <= m; i++) cin>>ee[i].u>>ee[i].v>>ee[i].w;

	for(int i = 1; i <= n; i++) f[i] = i;

	Kruskal();

	memset(fa, -1, sizeof(fa));

	fa[0] = 0;

	for(int i = 1; i <= n; i++) if(fa[i] == -1) dfs(i, 0);

	for(int i = 1; i <= n; i++) if(fa[i] == 0) add(i, 0, 0);

	dfs1(0);

	dfs2(0, 0);

	T.build(1, n, 1);

	cin>>q;

	for(int i = 1; i <= q; i++)

	{

		int x, y;

		cin>>x>>y;

		if(find(x) != find(y)) cout<<"-1\n";

		else cout<<T.Qrange(x, y)<<"\n";

	}

	return 0;

}