自动搬运

查看原文

来自洛谷，原作者为

	阿丑 ArrTue

搬运于2025-08-24 22:37:18，当前版本为作者最后更新于2022-10-24 07:44:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

前置知识：

根号分治。

简要题意：

• 给定一个 $n$ 个点 $m$ 条边的无向图，$q$ 次询问，每次询问给出两个点 $u,v$，询问有多少与 $u$ 相邻的点不与 $v$ 相邻也不是 $v$ 本身。
• $n,q\le2\times10^5$，$m\le7\times10^5$。

分析：

记点 $u$ 的度数为 $deg_u$。

记询问 $u,v$ 的答案为 $g_{u,v}$，则 $g_{u,v}$ 即为 $deg_u$ 减去 $u$ 与 $v$ 的公共相邻点个数，若 $u$ 与 $v$ 相邻，再减去 $1$。考虑如何求 $deg_u-g_{u,v}$，即 $u$ 与 $v$ 的公共相邻点个数，若 $u$ 与 $v$ 相邻，再加上 $1$。

考虑暴力。对于单次询问，找出所有与 $u$ 相邻的节点并将其打上标记；再找出所有与 $v$ 相邻的点，统计其中有标记的点的数量，即 $u$ 与 $v$ 公共相邻点的数量；若 $v$ 有标记，再加上 $1$。放一个代码片段方便理解。

memset(vis, 0, sizeof vis);
for(int z: ver[u]) {
	vis[z]=1;
}
int ans=vis[v];
for(int z: ver[v]) {
	ans+=vis[z];
}
printf("%d\n", deg[u]-ans);

单次询问更优的实现（对标记“懒”清空）可以做到 $\mathcal O(deg_u+deg_v)=\mathcal O(m)$，总复杂度 $\mathcal O(mq)$，期望 20pts。实测 88pts。

考虑优化。如果有两个询问完全相同，则不重复计算；即对询问去重。同时，对于同一个 $x$，我们统一处理所有 $u=x$ 的询问。这些询问只需打一次标记，复杂度 $\mathcal O(deg_x)$；遍历所有 $v$ 及其相邻边复杂度 $\mathcal O(m)$。对于所有的 $x$，总复杂度 $\mathcal O(\sum_x(deg_x+m)+q)=\mathcal O(nm+q)$，期望还是 20pts。实测 100pts。

上述过程中我们可以处理 $\mathcal O(n^2)$ 个询问，而总共只需要处理 $q$ 个询问。继续考虑优化。注意到 $deg_u-g_{u,v}$ 中，$u$ 和 $v$ 的地位是相等的，不妨让 $u$ 成为其中 $deg$ 较大者。于是，当 $deg_u<B$ 时，一次询问的复杂度为 $\mathcal O(deg_u+deg_v)=\mathcal O(B)$；当 $deg_u\ge B$ 时，因为 $\sum deg=2m$，所以最多存在 $\lfloor\frac {2m}B\rfloor$ 个不同的 $u$，按照上述优化遍历所有不同的 $u$ 对应的 $v$ 及其相邻边的复杂度为 $\mathcal O(\frac mB\times m)$。总复杂度 $\mathcal O(qB+\frac{m^2}B)$。

这个上界对所有的正实数 $B$ 都成立。可以取 $B=\frac m{\sqrt q}$，此时的上界是 $\mathcal O(m\sqrt q)$。在非特殊构造的数据下很难达到这个上界，期望 100pts。实测 100pts。

需要注意的是，这一步的优化保证了 $deg_u\ge deg_v$，而优化 1 没有，所以不能直接对优化 1 套用这里的复杂度分析。

由于对两种点的做法是一样的，所以代码比较简单。因为用了快排去重，所以代码的复杂度是 $\mathcal O(n+m\sqrt q+q\log q)$。空间复杂度 $\mathcal O(n+m+q)$。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
typedef long long ll;
const int mN=2e5+9, mM=7e5+9;
int n, m, q, deg[mN];

vector<int> ver[mN];

int ans[mN];
vector<pair<int, int> > qn[mN];

int vis[mN];

int main() {

	scanf("%d%d%d", &n, &m, &q);
	rep(i, 1, m) {
		int x, y;
		scanf("%d%d", &x, &y);
		++deg[x], ++deg[y];
		ver[x].push_back(y), ver[y].push_back(x);
	}
	rep(i, 1, q) {
		int x, y;
		scanf("%d%d", &x, &y);
		ans[i]=deg[x];	//ans 的剩余部分（deg[x]-g(x, y)）中，x y 地位相等 
		if(deg[x]<deg[y]) swap(x, y);	//保证 x 的 deg 更大 
		qn[x].push_back({y, i});
	}

	rep(x, 1, n) {
		sort(qn[x].begin(), qn[x].end());	//为了去重

		for(int y: ver[x]) {
			vis[y]=x;
		}
		int lst=0, lstans=0;
		//lst 记录上一个询问的 y, lstans 记录上一个询问的 deg[x]-g(x, y)
		for(auto ask: qn[x]) {
			const int y=ask.first, id=ask.second;
			if(y==lst) {
				ans[id]-=lstans;
				continue;
			}
			lstans=vis[y]==x;
			for(int z: ver[y]) {
				lstans+=vis[z]==x;
			}
			ans[id]-=lstans;
			lst=y;
		}
	}
	rep(i, 1, q) printf("%d\n", ans[i]);
	return 0;
}