crazy_cloud's Blog
0%

BOI2015 Network

Posted on Edited on In

题目大意

给定一颗 \(n\) 个点的无根树，求最少加多少条边使形成的图形任意删除一条边后都联通，边是无向的。

输出最少加边数和任意一种加边方案。注意不能加已出现的边。

\(3\leq n\leq 5\times10^5\)

题目分析

一道很套路的题目，想想还是写出来吧。

首先显然连接的边都是叶子肯定不会比其他方案要劣。然后问题变成选出尽量少的起点和终点都是叶子节点的路径覆盖完树上所有边。

这种题一般都是证明答案的上/下界然后对着构造。这题假设我们的叶子节点有 \(m\) 个，显然答案不会小于 \(\lceil\frac m2\rceil\)。因为每个叶子都需要一条边来使其与父亲双联通。

然后考虑构造一个答案为 \(\lceil\frac m2\rceil\) 的解。假如我们选取了一个节点 \(x\) 作为根，我们希望每个叶子都能和一个与它不属于同一棵子树（根节点儿子为根）的叶子匹配。令 \(\{a_k\}\) 表示其各个儿子节点子树内的叶子个数。我们相当于每次选择一组非零的 \(a_i,a_j\) 将它们都减 \(1\)，表示这两个子树内选择两个叶子匹配，执行到最后如果剩下了一个 \(1\) 就将其随便和一个其它子树的叶子匹配。

显然当最大的 \(a_i\) 的两倍超过 \(\sum a_i\) 时就不存在任何可行方案。那么我们就找一个类似“重心”的点（只不过是子树大小改为子树叶子个数）作为根，然后每次贪心地选取最大的一组 \(a_i,a_j\) 去匹配，各自减 \(1\) 放回去，直到无法执行就好了。

为什么这样一定能出解呢？考虑归纳证明，选取最大的 \(a_i,a_j\) 都减 \(1\) 塞回去，\(\{a_k\}\) 依然满足最大值两倍不超过总和。然后边界情况两个 \(1\) 是显然成立的。证毕。

时间复杂度 \(O(n\log n)\)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
#include <set>

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

const int N=500005;
const int E=N<<1;

int last[N],cnt[N],que[N],fa[N],size[N],deg[N];
int tov[E],nxt[E];
vector<int> leaf[N];
int n,tot,rt,head,tail,all;

struct comp
{
	inline bool operator()(const int &x,const int &y)const{return cnt[x]>cnt[y]||cnt[x]==cnt[y]&&x<y;}
};

set<int,comp> heap;

inline void insert(int x,int y){tov[++tot]=y,nxt[tot]=last[x],last[x]=tot;}

int core(int og)
{
	int rets=n+1,ret=0,i,x,y,tmp;
	for (head=0,fa[que[tail=1]=og]=0;head<tail;)
		for (size[x=que[++head]]=0,i=last[x];i;i=nxt[i])
			if ((y=tov[i])!=fa[x]) size[fa[que[++tail]=y]=x]=1;
	for (head=1;head<=tail;++head) size[que[head]]^=1;
	for (head=tail;head>1;--head) size[fa[que[head]]]+=size[que[head]];
	for (head=1;head<=tail;++head)
	{
		for (tmp=size[og]-size[x=que[head]],i=last[x];i;i=nxt[i])
			if ((y=tov[i])!=fa[x]) tmp=max(tmp,size[y]);
		if (tmp<rets&&deg[x]>1) rets=tmp,ret=x;
	}
	return ret;
}

void dfs(int x,int src)
{
	int son=0;
	for (int i=last[x],y;i;i=nxt[i])
		if ((y=tov[i])!=fa[x]) fa[y]=x,dfs(y,src),++son;
	if (!son) leaf[src].push_back(x);
}

void calc()
{
	all=0;
	for (int i=1;i<=n;++i)
	{
		all+=cnt[i]=(int)leaf[i].size();
		if (cnt[i]) heap.insert(i);
	}
	printf("%d\n",all+1>>1);
	for (;!heap.empty();)
	{
		int x=*heap.begin();heap.erase(heap.begin());
		if (heap.empty())
		{
			int y=leaf[x][--cnt[x]];
			if (fa[y]==rt)
			{
				int z=0;
				for (z=1;z<=n;++z) if (z!=y&&fa[z]==rt) break;
				printf("%d %d\n",y,z);
			}
			else printf("%d %d\n",y,rt);
		}
		else
		{
			int y=*heap.begin();heap.erase(heap.begin());
			printf("%d %d\n",leaf[x][--cnt[x]],leaf[y][--cnt[y]]);
			if (cnt[y]) heap.insert(y);
		}
		if (cnt[x]) heap.insert(x);
	}
}

int main()
{
	freopen("network.in","r",stdin),freopen("network.out","w",stdout);
	n=read();
	for (int i=1,x,y;i<n;++i) x=read(),y=read(),insert(x,y),insert(y,x),++deg[x],++deg[y];
	for (int i=1;!rt&&i<=n;++i) if (deg[i]>1) rt=i;
	fa[rt=core(rt)]=0;
	for (int i=last[rt],y;i;i=nxt[i]) fa[y=tov[i]]=rt,dfs(y,y);
	calc();
	fclose(stdin),fclose(stdout);
	return 0;
}