[USACO18JAN]MooTube

[USACO18JAN]MooTube


首先我们先理解并转化模型。

这道题问的是:一棵树,\(n\)个点上给边权,定义两个点的相关性为简单路径上最小边权。给一些询问,让你回答所有点与\(v\)的相关性不小于给的\(k\)的有多少个?


这道题一看到最小边权,我会想到LCA,通过DP求解出每个点到\(k\)级祖先的路径上的最小值。看起来这道题可以转化为树的基本应用,可是如果对于一个节点\(v\)而言,要统计的不仅仅是它的祖先及其子孙,还要统计\(v\)本身的儿子,以上做法只能统计它的祖先。


跑换根行吗?很明显,这道题是一个多次询问的动态问题,我们可以考虑:

以节点编号为第一维,以最小相关度为第二维,然而边权高达\(10^9\),离散化后也有\(O(n^2)\)。每一次换根时间复杂度都不菲。


不过刚刚的离散化提示我们,其实可以离线去做这件事情。如果一条边权是\(w\)的边,小于某一个\(k\),那么当存在\(k'(k'>k)\),它也小。我们可以考虑每次搜索的过程,如果这条边已经小了,那么无论怎样都不会遍历这条边以及后续的边,因此很自然地,我们对查询按\(k\)进行排序。

又由于这是一颗树,考虑最小生成树的原理,每一条边实际上都是在连接两个不同的联通分量,因此如果将一条边断掉,被分出来的两个分量互不干扰相互独立的。这又会想到可以使用并查集使每个点所在块连起来。

所以,我们对所有的边按边权排序,当下一个查询来的时候从小到依次看边权是否比\(k_i\)小,拆边。

拆边其实挺困难的,我们不妨换一种思路:从大到小枚举,连接。

至此,这道题解法已经讲清楚了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#define CLR(x,y) memset(x,y,sizeof(x))
#define FOR(i,x,y) for(register int i=x;i<=y;++i)
using namespace std;

const int N = 100000 + 5;

typedef long long LL;

struct Edge
{
	int u, v, w;
	inline bool operator <(const Edge &lhs) const
	{
		return w > lhs.w;
	}
} e[N];
struct query
{
	int k, v, num;
	inline bool operator <(const query &rhs) const
	{
		return k > rhs.k;
	}
} q[N];
int n, Q, fa[N], siz[N], ans[N];
template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
	return;
}
int get(int x)
{
	if(fa[x] == x) return x;
	fa[x] = get(fa[x]);
	siz[x] = siz[fa[x]];
	return fa[x];
}
void merge(int u, int v)
{
	int v1 = get(u), v2 = get(v);
	if(siz[v1] > siz[v2]) swap(v1, v2);
	fa[v1] = v2;
	siz[v2] += siz[v1];
	siz[v1] = siz[v2];
	return;
}
int main()
{
	read(n), read(Q);
	FOR(i, 1, n) fa[i] = i, siz[i] = 1;
	for(int i = 1; i < n; ++ i)
		read(e[i].u), read(e[i].v), read(e[i].w);		
	sort(e + 1, e + n);
	for(int i = 1; i <= Q; ++ i)
	{
		read(q[i].k), read(q[i].v);
		q[i].num = i;
	}
	sort(q + 1, q + Q + 1);
	int pt = 1;//开区间 
	FOR(i, 1, Q)
	{
		while(e[pt].w >= q[i].k) 
		{
			merge(e[pt].u, e[pt].v);
			++ pt;
		}
		int u = q[i].v;
		get(u);
		ans[q[i].num] = siz[u] - 1;// the exception is itself
	}
	FOR(i, 1, Q) printf("%d\n", ans[i]);
	return 0;
}

总结

这道题让我回顾几个做题方法:

  • 所有查询的问题可以离线做(在线的还没遇到)
  • 当题目求所有比一个数大的数量时,可以求比它小的数量;正序做困难,倒序做。
  • 最小生成树边连接两个不同的联通分量,结合并查集可以事半功倍。
上一篇:『Mivik的萌新赛 & Chino的比赛 2020』T2 题解 Galgame


下一篇:unordered_map赋值以及常用成员函数