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

「APIO2010」巡逻 - 动规/贪心

方法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;
}
0%