P11252 题解

发现题解区的代码有点抽象啊，那就自己写一篇吧。

解题思路

设需要进行 $x$ 次区域建设，由于每次区域建设会增加 $1$ 个点和 $3$ 条边，则最终会有 $n+(n-3)+3x=2n+3x-3$ 条边，$n+x$ 个点。需要拆成两棵树，则需要 $2(n+x-1)=2n+2x-2$ 条边，有式子：

解得:

所以，我们至少进行 $1$ 次区域建设即可。

考虑如何只进行一次区域建设就满足条件。假设将第一棵树的边染成红色，将第二棵树的边染成蓝色。由于每一棵树都要覆盖到所有的点，所有点连出去的边都必须包含红蓝两种颜色。那么，对于度数为 $2$ 的点，连出去的边必为一红一蓝，我们应当优先处理这些点。

我们可以这样处理多少次呢？当所有点度数都 $\geq 3$ 时，我们就不能继续这样处理了（注意此时我们区域建设新增的点和边已经加入到图里了）。设此时有 $n'$ 个点，那么总边数 $\geq\dfrac{3n'}{2}$，而拆成两棵树需要 $2(n'-1)$ 条边，所以有：

解得：

所以，在点数 $>4$ 时，我们一定能找到一个度为 $2$ 的点。当点数 $=4$ 时，进行特殊构造即可。如图：

综上，我们解决问题的全过程为：建图，找到所有度数为 $2$ 的点并将两条边染成红色和蓝色，最后剩三个点区域建设并特殊构造即可。

代码实现

建图： 用 set<int> e[maxN] 来保存每个点与哪些点相连，用 int deg[maxN] 来保存每个点的度数。

set<int> e[maxN];
int deg[maxN];
void construct_two_trees(int n, std::vector<int> U, std::vector<int> V)
{
    for(int i=0;i<=n-2;i++)
	{
		e[i].insert(i+1);
		e[i+1].insert(i);
		deg[i]++;
		deg[i+1]++;
	}
	e[0].insert(n-1);
	e[n-1].insert(0);
	deg[0]++;
	deg[n-1]++;
	for(int i=0,j=0;i<U.size();i++,j++)
	{
		e[U[i]].insert(V[i]);
		e[V[i]].insert(U[i]);
		deg[U[i]]++;
		deg[V[i]]++;
	}
    /**/
}

处理度数为 $2$ 的点：

类似于拓扑排序，用 queue<int> q 来保存每个度数为 $2$ 的点，每次取出队头，对队头进行操作，并将与之相连的两个点度数减一，如果又出现了度数为 $2$ 的点，加入队尾。最后剩三个点。

queue<int> q;
void construct_two_trees(int n, std::vector<int> U, std::vector<int> V)
{
    /**/
    for(int i=0;i<n;i++)
	{
		if(deg[i]==2)
		{
			q.push(i);
		}
	}
	for(int i=0;i<n-3;i++)
	{
		int now=q.front();
		q.pop();
		int l=*e[now].begin();
		int r=*e[now].rbegin();
		red.push_back({now,l});
		blue.push_back({now,r});
		e[l].erase(now);
		e[r].erase(now);
		deg[l]--;
		deg[r]--;
		if(deg[l]==2) q.push(l);
		if(deg[r]==2) q.push(r);
	}
    /**/
}

区域建设：

queue<int> q;
void construct_two_trees(int n, std::vector<int> U, std::vector<int> V)
{
    /**/
    int a=q.front();q.pop();
	int b=q.front();q.pop();
	int c=q.front();q.pop();
	int d=add_vertex(a,b,c);
	red.push_back({a,b});red.push_back({b,d});red.push_back({d,c});
	blue.push_back({a,c});blue.push_back({a,d});blue.push_back({b,c});
	report(red);
	report(blue);
	return;
}

时间复杂度 $O(n \log n)$，完整代码如下：

#include<bits/stdc++.h>
#include"island.h"//提交时这句话千万别加！！！
using namespace std;
int add_vertex(int a, int b, int c);
void report(std::vector<std::array<int, 2>> tree);
const int maxN=200005;
vector<array<int,2>> red,blue;
set<int> e[maxN];
int deg[maxN];
queue<int> q;
void construct_two_trees(int n, std::vector<int> U, std::vector<int> V)
{
	for(int i=0;i<=n-2;i++)
	{
		e[i].insert(i+1);
		e[i+1].insert(i);
		deg[i]++;
		deg[i+1]++;
	}
	e[0].insert(n-1);
	e[n-1].insert(0);
	deg[0]++;
	deg[n-1]++;
	for(int i=0,j=0;i<U.size();i++,j++)
	{
		e[U[i]].insert(V[i]);
		e[V[i]].insert(U[i]);
		deg[U[i]]++;
		deg[V[i]]++;
	}
	for(int i=0;i<n;i++)
	{
		if(deg[i]==2)
		{
			q.push(i);
		}
	}
	for(int i=0;i<n-3;i++)
	{
		int now=q.front();
		q.pop();
		int l=*e[now].begin();
		int r=*e[now].rbegin();
		red.push_back({now,l});
		blue.push_back({now,r});
		e[l].erase(now);
		e[r].erase(now);
		deg[l]--;
		deg[r]--;
		if(deg[l]==2) q.push(l);
		if(deg[r]==2) q.push(r);
	}
	int a=q.front();q.pop();
	int b=q.front();q.pop();
	int c=q.front();q.pop();
	int d=add_vertex(a,b,c);
	red.push_back({a,b});red.push_back({b,d});red.push_back({d,c});
	blue.push_back({a,c});blue.push_back({a,d});blue.push_back({b,c});
	report(red);
	report(blue);
	return;
}