【树上倍增树上差分】P9246 [蓝桥杯 2023 省 B] 砍树|普及+

闻缺陷则喜何志丹

1809人浏览 · 2025-09-08 17:00:00

闻缺陷则喜何志丹 · 2025-09-08 17:00:00 发布

本文涉及知识点

倍增算法(multiply)、树上倍增、最近公共祖先(LCA)
C++差分数组

P9246 [蓝桥杯 2023 省 B] 砍树

题目描述

给定一棵由 $n$ 个结点组成的树以及 $m$ 个不重复的无序数对 $\left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right),\ldots,\left(a_{m},b_{m}\right)$ ，其中 $a_{i}$ 互不相同， $b_{i}$ 互不相同， $a_{i} \neq b_{j}(1 \leq i,j \leq m)$ 。

小明想知道是否能够选择一条树上的边砍断，使得对于每个 $\left(a_{i},b_{i}\right)$ 满足 $a_{i}$ 和 $b_{i}$ 不连通，如果可以则输出应该断掉的边的编号 (编号按输入顺序从 $1$ 开始)，否则输出 -1。

输入格式

输入共 $n + m$ 行，第一行为两个正整数 $n, m$ 。

后面 $n - 1$ 行，每行两个正整数 $x_{i},y_{i}$ 表示第 $i$ 条边的两个端点。

后面 $m$ 行，每行两个正整数 $a_{i},b_{i}$ 。

输出格式

一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【样例说明】

断开第 $2$ 条边后形成两个连通块： ${3,4\},\{1,2,5,6\}$ ，满足 $3$ 和 $6$ 不连通， $4$ 和 $5$ 不连通。

断开第 $4$ 条边后形成两个连通块： ${1,2,3,4\},\{5,6\}$ ，同样满足 $3$ 和 $6$ 不连通， $4$ 和 $5$ 不连通。

$4$ 编号更大，因此答案为 $4$ 。

【评测用例规模与约定】

对于 $\%$ 的数据，保证 $\leq 10^3$ 。

对于 $\%$ 的数据，保证 $\leq 10^{5}$ ， $\leq m \leq \frac{n}{2}$ 。

蓝桥杯 2023 省赛 B 组 J 题。

[蓝桥杯 2023 省 B] 砍树树上差分 LCA

一，以0为根，BFS求出个节点的层次，根节点层次是0。
二，求各节点的父节点par。
三，枚举a、b。令ai和bi的最近公共祖先是ab。则diff[a]++,diff[b]++,diff[ab]-=2。
四，按层次从大到小处理各节点。如果diff[cur] == m，则cur到父节点是合法边之一。diff[par] += diff[cur]。
五，枚举序号最大的可删除边。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t);
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	cin >> n;
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
	vector<T> ret;
	T tmp;
	while (cin >> tmp) {
		ret.emplace_back(tmp);
		if ('\n' == cin.get()) { break; }
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

template<int N = 1'000'000>
class COutBuff
{
public:
	COutBuff() {
		m_p = puffer;
	}
	template<class T>
	void write(T x) {
		int num[28], sp = 0;
		if (x < 0)
			*m_p++ = '-', x = -x;

		if (!x)
			*m_p++ = 48;

		while (x)
			num[++sp] = x % 10, x /= 10;

		while (sp)
			*m_p++ = num[sp--] + 48;
		AuotToFile();
	}
	void writestr(const char* sz) {
		strcpy(m_p, sz);
		m_p += strlen(sz);
		AuotToFile();
	}
	inline void write(char ch)
	{
		*m_p++ = ch;
		AuotToFile();
	}
	inline void ToFile() {
		fwrite(puffer, 1, m_p - puffer, stdout);
		m_p = puffer;
	}
	~COutBuff() {
		ToFile();
	}
private:
	inline void AuotToFile() {
		if (m_p - puffer > N - 100) {
			ToFile();
		}
	}
	char  puffer[N], * m_p;
};

template<int N = 1'000'000>
class CInBuff
{
public:
	inline CInBuff() {}
	inline CInBuff<N>& operator>>(char& ch) {
		FileToBuf();
		while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车
		ch = *S++;
		return *this;
	}
	inline CInBuff<N>& operator>>(int& val) {
		FileToBuf();
		int x(0), f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行		
		return *this;
	}
	inline CInBuff& operator>>(long long& val) {
		FileToBuf();
		long long x(0); int f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行
		return *this;
	}
	template<class T1, class T2>
	inline CInBuff& operator>>(pair<T1, T2>& val) {
		*this >> val.first >> val.second;
		return *this;
	}
	template<class T1, class T2, class T3>
	inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
		return *this;
	}
	template<class T1, class T2, class T3, class T4>
	inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
		return *this;
	}
	template<class T = int>
	inline CInBuff& operator>>(vector<T>& val) {
		int n;
		*this >> n;
		val.resize(n);
		for (int i = 0; i < n; i++) {
			*this >> val[i];
		}
		return *this;
	}
	template<class T = int>
	vector<T> Read(int n) {
		vector<T> ret(n);
		for (int i = 0; i < n; i++) {
			*this >> ret[i];
		}
		return ret;
	}
	template<class T = int>
	vector<T> Read() {
		vector<T> ret;
		*this >> ret;
		return ret;
	}
private:
	inline void FileToBuf() {
		const int canRead = m_iWritePos - (S - buffer);
		if (canRead >= 100) { return; }
		if (m_bFinish) { return; }
		for (int i = 0; i < canRead; i++)
		{
			buffer[i] = S[i];//memcpy出错			
		}
		m_iWritePos = canRead;
		buffer[m_iWritePos] = 0;
		S = buffer;
		int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
		if (readCnt <= 0) { m_bFinish = true; return; }
		m_iWritePos += readCnt;
		buffer[m_iWritePos] = 0;
		S = buffer;
	}
	int m_iWritePos = 0; bool m_bFinish = false;
	char buffer[N + 10], * S = buffer;
};

class CNeiBo
{
public:
	static vector<vector<int>> Two(int n, const vector<pair<int, int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& [i1, i2] : edges)
		{
			vNeiBo[i1 - iBase].emplace_back(i2 - iBase);
			if (!bDirect)
			{
				vNeiBo[i2 - iBase].emplace_back(i1 - iBase);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Two(int n, const vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<std::pair<int, int>>> Three(int n, const vector<tuple<int, int, int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& [u, v, w] : edges)
		{
			vNeiBo[u - iBase].emplace_back(v - iBase, w);
			if (!bDirect)
			{
				vNeiBo[v - iBase].emplace_back(u - iBase, w);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};

class CBFSLeve {
public:
	static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {
		vector<int> leves(neiBo.size(), -1);
		for (const auto& s : start) {
			leves[s] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			for (const auto& next : neiBo[start[i]]) {
				if (-1 != leves[next]) { continue; }
				leves[next] = leves[start[i]] + 1;
				start.emplace_back(next);
			}
		}
		return leves;
	}
	template<class NextFun>
	static vector<int> Leve(int N, NextFun nextFun, vector<int> start) {
		vector<int> leves(N, -1);
		for (const auto& s : start) {
			leves[s] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			auto nexts = nextFun(start[i]);
			for (const auto& next : nexts) {
				if (-1 != leves[next]) { continue; }
				leves[next] = leves[start[i]] + 1;
				start.emplace_back(next);
			}
		}
		return leves;
	}
	static vector<vector<int>> LeveNodes(const vector<int>& leves) {
		const int iMaxLeve = *max_element(leves.begin(), leves.end());
		vector<vector<int>> ret(iMaxLeve + 1);
		for (int i = 0; i < leves.size(); i++) {
			ret[leves[i]].emplace_back(i);
		}
		return ret;
	};
	static vector<int> LeveSort(const vector<int>& leves) {
		const int iMaxLeve = *max_element(leves.begin(), leves.end());
		vector<vector<int>> leveNodes(iMaxLeve + 1);
		for (int i = 0; i < leves.size(); i++) {
			leveNodes[leves[i]].emplace_back(i);
		}
		vector<int> ret;
		for (const auto& v : leveNodes) {
			ret.insert(ret.end(), v.begin(), v.end());
		}
		return ret;
	};
};
class CParents
{
public:
	CParents(vector<int>& vParent, long long iMaxDepth)
	{
		int iBitNum = 0;
		for (; iMaxDepth; iBitNum++) {
			const auto mask = 1LL << iBitNum;
			if (mask & iMaxDepth) { iMaxDepth = iMaxDepth ^ mask; }
		}
		const int n = vParent.size();
		m_vParents.assign(iBitNum + 1, vector<int>(n, -1));
		m_vParents[0] = vParent;
		//树上倍增
		for (int i = 1; i < m_vParents.size(); i++)
		{
			for (int j = 0; j < n; j++)
			{
				const int iPre = m_vParents[i - 1][j];
				if (-1 != iPre)
				{
					m_vParents[i][j] = m_vParents[i - 1][iPre];
				}
			}
		}
	}
	int GetParent(int iNode, int iDepth)const
	{
		int iParent = iNode;
		for (int iBit = 0; iBit < m_vParents.size(); iBit++)
		{
			if (-1 == iParent)
			{
				return iParent;
			}
			if (iDepth & (1 << iBit))
			{
				iParent = m_vParents[iBit][iParent];
			}
		}
		return iParent;
	}
	inline int GetBitCnt()const { return m_vParents.size(); };
	inline const int& GetPow2Parent(int iNode, int n)const {
		return m_vParents[n][iNode];
	}
	//在leftNodeExclude的1到rightLeve级祖先中查找符合pr的最近祖先
	template<class _Pr>
	int FindFirst(int leftNodeExclude, int rightLeve, _Pr pr) {
		for (int iBit = GetBitCnt() - 1; iBit >= 0; iBit--) {
			const int iMask = 1 << iBit;
			if (!(iMask & rightLeve)) { continue; }
			if (pr(m_vParents[iBit][leftNodeExclude])) {
				return BFindFirst(leftNodeExclude, iBit, pr);
			}
			leftNodeExclude = m_vParents[iBit][leftNodeExclude];
		}
		return -1;
	}
	//在node的0到rightLeve级祖先中查找符合pr的最远祖先比node高多少层次,这些层次必须存在
	template<class _Pr>
	int FindEnd(int node, int rightLeve, _Pr pr) {
		int leve = 0;
		for (int iBit = GetBitCnt() - 1; iBit >= 0; iBit--) {
			const int iMask = 1 << iBit;
			if (!(iMask & rightLeve)) { continue; }
			if (!pr(m_vParents[iBit][node])) {
				return leve + BFindEnd(node, iBit, pr);
			}
			node = m_vParents[iBit][node];
			leve = leve ^ iMask;
		}
		return leve;
	}
protected:
	//在leftNodeExclude的1到2^pow^级祖先中查找符合pr的最近祖先
	template<class _Pr>
	int BFindFirst(int leftNodeExclude, int pow, _Pr pr) {
		while (pow > 0) {
			const int& mid = m_vParents[pow - 1][leftNodeExclude];
			if (pr(mid)) {
			}
			else {
				leftNodeExclude = mid;
			}
			pow--;
		}
		return m_vParents[0][leftNodeExclude];
	}
	//在node的[0,2^pow^-1]级祖先中寻找符合的最后一个
	template<class _Pr>
	int BFindEnd(int node, int pow, _Pr pr) {
		int leve = 0;
		while (pow > 0) {
			pow--;
			const int& mid = m_vParents[pow][node];
			if (pr(mid)) {
				node = mid;
				leve = leve ^ (1 << pow);
			}
			else {

			}

		}
		return leve;
	}
	vector<vector<int>> m_vParents;
};

class C2Parents : public CParents
{
public:
	C2Parents(vector<int>& vParent, const vector<int>& vDepth) :m_vDepth(vDepth)
		, CParents(vParent, *std::max_element(vDepth.begin(), vDepth.end()))
	{
	}
	int GetPublicParent(int iNode1, int iNode2)const
	{
		int leve0 = m_vDepth[iNode1];
		int leve1 = m_vDepth[iNode2];
		if (leve0 < leve1)
		{
			iNode2 = GetParent(iNode2, leve1 - leve0);
			leve1 = leve0;
		}
		else
		{
			iNode1 = GetParent(iNode1, leve0 - leve1);
			leve0 = leve1;
		}
		if (iNode1 == iNode2) { return iNode1; }
		for (int iBit = GetBitCnt() - 1; iBit >= 0; iBit--) {
			const int iMask = 1 << iBit;
			if (iMask & leve0) {
				const int i1 = GetPow2Parent(iNode1, iBit);
				const int i2 = GetPow2Parent(iNode2, iBit);
				if (i1 == i2) {
					while (iBit > 0) {
						const int i3 = GetPow2Parent(iNode1, iBit - 1);
						const int i4 = GetPow2Parent(iNode2, iBit - 1);
						if (i3 != i4) {
							iNode1 = i3; iNode2 = i4;
						}
						iBit--;
					}
					return GetPow2Parent(iNode1, 0);
				}
				else {
					iNode1 = i1; iNode2 = i2; leve0 -= iMask;
				}
			}
		}
		return iNode1;
	}
protected:

	vector<vector<int>> m_vParents;
	const vector<int> m_vDepth;
};

class Solution {
public:
	int Ans(const int N, vector<pair<int, int>>& edge, vector<pair<int, int>>& ab) {
		const int M = ab.size();
		for (auto& [u, v] : edge) {
			u--, v--;
		}
		for (auto& [a, b] : ab) { a--; b--; }
		auto neiBo = CNeiBo::Two(N, edge, false);
		auto leves = CBFSLeve::Leve(neiBo, { 0 });
		auto leveNodes = CBFSLeve::LeveNodes(leves);
		vector<int> par(N, -1);
		for (auto& [u, v] : edge) {
			if (leves[u] > leves[v]) {
				swap(u, v);
			}
			par[v] = u;
		}
		C2Parents pars(par, leves);
		vector<int> diff(N);
		for (const auto& [a, b] : ab) {
			const int ab = pars.GetPublicParent(a, b);
			diff[a]++; diff[b]++; diff[ab] -= 2;
		}
		vector<bool> canDel(N);
		for (auto it = leveNodes.rbegin(); it != leveNodes.rend(); ++it) {
			for (const auto& cur : *it) {
				canDel[cur] = M == diff[cur];
				const int iPar = par[cur];
				if (-1 == iPar) { continue; }
				diff[iPar] += diff[cur];
			}
		}
		for (int i = edge.size(); i >= 1; i--) {
			if (canDel[edge[i - 1].second]) { return i; }
		}
		return -1;
	}
};


int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	//ios::sync_with_stdio(0); cin.tie(nullptr);
	CInBuff<> in; COutBuff<10'000'000> ob;	
	int N, M;
	in >> N >> M;
	auto edge = in.Read <pair<int,int> > (N-1);
	auto ab = in.Read<pair<int,int>>(M);
#ifdef _DEBUG		
		printf("N=%d", N);
		Out(edge, ",edge=");
		Out(ab, ",ab=");
		//Out(B, "B=");
		//Out(que, "que=");
		//Out(B, "B=");
#endif // DEBUG	
		auto res = Solution().Ans(N,edge,ab);
		cout << res;
	return 0;
}

单元测试

int N;
		vector<pair<int, int>> edge;
		vector<pair<int,int>>ab;
		TEST_METHOD(TestMethod01)
		{
			N = 6, edge = { {1,2},{2,3},{4,3},{2,5},{6,5} }, ab = { {3,6},{4,5} };
			auto res = Solution().Ans(N, edge, ab);
			AssertEx(4, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功