隐藏
「APIO2010」巡逻 - 动规/贪心 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

「APIO2010」巡逻 - 动规/贪心

发表于 更新于 分类于 Valine：

方法1：贪心

根据题目描述，很直观的可以想到一个贪心算法：
当k==1时选出树的直径（最长链），如图有一棵树：


图1的连接方式必定比图2更优
图1
图2
因此我们先找出树的直径，当k==1时直接得到答案。
对于k==2，此时我们已经有了一条直径，若把这条直径连成环，原树就变成了一个环套树，环套树还要合并任意两个结点，我们可以得到限制条件：
$\quad$①环越大越好
$\quad$②新环与原环相交部分越少越好
那么即可将第一次的到的环边权改为-1，再找一次最大的环，得到答案。
为什么这样是正确的？
因为将重叠部分重新添加了回去，故重叠部分对答案的影响消除了，同时满足了两个限制条件。

优化

我们发现找环并不必要。
因为我们添加的边不可能与另一个环相交。
故只需要找出直径并将直径上的边权改为-1，再重新求出直径即可。

方法2：树形动规

根据题目描述与数据范围，这题很难想到树形动规这一种解法。
考虑到上诉贪心做法，当两条直径相交时，减去相交部分，与选出两条不相交的直径等价（如图黑色的环与红色环等价）。

根据总结本P55树形动规的总结，树形动规可以找出树上的一个或多个图形。
首先列出所有的可能情况。（注：环链指差一条边成为环的链）

  • 情况1

    如图，即当前结点的所有后代中有两个环链。（规定必须是后代，不包含自己）
    环链的求法和直径一样，即为当前结点最长链+次长链。
    故维护最长链d1[]与次长链d2[]。
    易得当前结点子树中环链的最大长度：故统计当前结点的子结点Circle[]的最大c1[]与次大c2[]，使用$c1[i]+c2[i]$更新答案。
  • 情况2

    如图，即其中一个环链是另一个环链的祖先。（规定必须严格祖先后代关系，不能相交）
    根据上图，选择箭头所指点统计答案较为便捷。
    当前已经有了第一个环链（后代），但是要构成第二个环链（祖先），需要讨论环链如何构成。（注：du表示来自父亲的最长链）
    $\quad$ ①

    $\quad$ 如图，最长链与次长链均不来自环链，du+d1与d1+d2可以构成两个环链。
    $\quad$ 使用$max(d2[Now],du[Now])+d1[Now]+Circle[Next]$更新答案。
    $\quad$
    $\quad$ ②

    $\quad$ 如图，最长链来自环链（判断方法：d1[Next]+1==d1[Now]），那么有了环链，就不能使用d1+d2更新答案。
    $\quad$ 为了构成祖先环链，我们还需维护第三长链d3[]，那么du+d2与d2+d3可以构成两个环链。
    $\quad$ 使用$max(d3[Now],du[Now])+d2[Now]+Circle[Next]$更新答案。
    $\quad$
    $\quad$ ⑨

    $\quad$ 类似的，次长链来自环链（判断方法：d1[Next]+1==d2[Now]），不能使用d1+d2更新答案。
    $\quad$ du+d2与d2+d3可以构成两个环链。
    $\quad$ 使用$max(d3[Now],du[Now])+d1[Now]+Circle[Next]$更新答案。
    $\quad$
    那么情况2就讨论完了。
  • 情况3

    如图，两个环链有交点。（边不相交，点相交）
    在交点处统计答案较为便捷。
    故得到以下图形：

    由图，还需要维护第四长链d4[]
    显然可以使用$d1[Now]+d2[Now]+d3[Now]+max(d4[Now],du[Now])$更新答案

整理一下需要维护的信息

  • d1[]~d4[]：最长链~第四长链
  • du[]：来自父亲的最长链
  • Circle[]：当前结点子树中环链的最大长度
  • c1[]、c2[]：当前结点儿子的Circle值最大与次大

最后输出$2(n-1)-(ans2-ans-2)$即可。
至此，问题完美解决。

扩展：若求三个或k个环链怎么办？
若k为常数：继续讨论呗
否则：还是按照标准题解写吧。。。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
//树形动规
const int maxn=100005;
int father[maxn],d1[maxn],d2[maxn],d3[maxn],d4[maxn],du[maxn],From1[maxn],Circle[maxn],c1[maxn],c2[maxn];
int n,k,ans=0;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
	edges[x].push_back(y);
}
void TreeDp(int Now,int fa) {
	father[Now]=fa;
	for(int i=0; i<edges[Now].size(); i++) {
		int Next=edges[Now][i];
		if(Next==fa)continue;
		TreeDp(Next,Now);
		if(d1[Next]+1>d1[Now])d4[Now]=d3[Now],d3[Now]=d2[Now],d2[Now]=d1[Now],d1[Now]=d1[Next]+1,From1[Now]=Next;
		else if(d1[Next]+1>d2[Now])d4[Now]=d3[Now],d3[Now]=d2[Now],d2[Now]=d1[Next]+1;
		else if(d1[Next]+1>d3[Now])d4[Now]=d3[Now],d3[Now]=d1[Next]+1;
		else if(d1[Next]+1>d4[Now])d4[Now]=d1[Next]+1;
		Circle[Now]=max(Circle[Next],Circle[Now]);
		if(Circle[Next]>c1[Now]) {
			c2[Now]=c1[Now];
			c1[Now]=Circle[Next];
		} else if(Circle[Next]>c2[Now])c2[Now]=Circle[Next];
	}
	Circle[Now]=max(Circle[Now],d1[Now]+d2[Now]);
	ans=max(ans,c1[Now]+c2[Now]); //情况1
}
void TreeDp2(int Now) {
	if(father[Now]) { //不为根
		if(From1[father[Now]]==Now)du[Now]=max(du[father[Now]],d2[father[Now]])+1; //父亲最长链来自自己
		else du[Now]=max(du[father[Now]],d1[father[Now]])+1;
	}
	for(int i=0; i<edges[Now].size(); i++) {
		int Next=edges[Now][i];
		if(Next==father[Now])continue;
		TreeDp2(Next);
		if(d1[Now]!=d1[Next]+1&&d2[Now]!=d1[Next]+1)ans=max(ans,max(d2[Now],du[Now])+d1[Now]+Circle[Next]); //情况2.1
		if(d1[Now]==d1[Next]+1)ans=max(ans,max(d3[Now],du[Now])+d2[Now]+Circle[Next]); //情况2.2
		if(d2[Now]==d1[Next]+1)ans=max(ans,max(d3[Now],du[Now])+d1[Now]+Circle[Next]); //情况2.3
	}
	ans=max(ans,d1[Now]+d2[Now]+d3[Now]+max(d4[Now],du[Now])); //情况3
}
int main() {
	n=Get_Int();
	k=Get_Int();
	for(int i=1; i<n; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge(x,y);
		AddEdge(y,x);
	}
	TreeDp(1,0);
	if(k==1) {
		printf("%d\n",2*(n-1)-(Circle[1]-1));
		return 0;
	}
	TreeDp2(1);
	printf("%d\n",2*(n-1)-(ans*2-ans-2));
	return 0;
}
相关文章
姥爷们赏瓶冰阔落吧~