[APIO2010]巡逻

这题就是求在树中添加1条或者2条边，使得从第一个点开始走，在必须经过新添加的边的前提下，经过每个点且回到源点的最小长度。

加1条边

如果我们不加边的话，那么很显然，总的长度就是2*(n-1)。做这题的时候比较容易想到，如果添加1条边，那么连接最远的两个点。

事实上这确实是有点道理的：假设叶子A和叶子B的最近公共祖先为P。那么，如果我们新建边(A, B)，则可以减少dist(A, B)-1的长度。因此，如果我们把树中最远的两个点连起来，那么就减少了树直径-1的的路程。

加2条边

一开始我的想法是加完1条边后，再在剩余的图中找一条最长的路径，扣掉即可。但实际上，样例数据十分好地把这个想法扼杀了。

如果我们找两条路径，那么根据上面的理论，我们可以减去这两条路径长度-2。但是如果这两条路径有公共部分，那么就必须再加上公共部分的长度，因为公共部分会多走一次。

也就是说，如果我们要找的是两条链，使得它们(总长度之和-公共部分长度)最大。其实，这个可以转化为树的直径……

树的直径

传统的求树的直径的方法，就是从树的任一点开始找到离它最远的点，再从那个点开始找到离它最远的点，那么这一次经过的路径就是树的直径。证明也十分显然，这里就不啰嗦了。这样子的复杂度是O(2n)，常常用2次DFS或者BFS实现。

注意到我们每一次走过一个点，路径长度就+1。然而像这题，如果我们有公共部分，那么应该受到惩罚，也就是长度-1。因此，我们可以将整棵大树直径上的每一条边的权值改成-1，这样经过它的时候就受到了惩罚。这样，第二次做变相（有的权为-1）的树的直径，两次树的直径之和就是所求的。

显然之前两次DFS或者BFS的方法不适合带有负权的树。我们可以考虑另外一种递归的做法（其实是树形DP）：

何为直径？两条半径相加。因此对于某个点，我们把它当作“圆心”，计算“半径”，那么最长的两条“半径”之和就是直径。

实现？ 

DIAMETER(u, ANS)
  maxr1 = 0
  maxr2 = 0
  foreach v∈u's sons
    d = DIAMETER(v, ANS) + weight of (u, v)
    if d > maxr1
      maxr2 = maxr1
      maxr1 = d
    else if d > maxr2
      maxr2 = d
  ANS = max(ANS, maxr1+maxr2)
  return maxr1

代码 

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

#include <cstdio>
#include <cstring>
 
const int INF = 0x7FFFFFFF;
const int MAXN = 100000;
struct Edge
{
  int v, w;
  Edge* next;
} g[MAXN*2];
int link_size;
Edge* header[MAXN];
inline void add_edge(const int x, const int y, const int w = 1)
{
  Edge* node = g+(link_size++);
  node->v = y;
  node->w = w;
  node->next = header[x];
  header[x] = node;
}
int n, m, max, fm1, fm2, fm[MAXN];
Edge *em1, *em2;
 
int diameter(const int i, const int parent = -1)
{
  int m1 = 0, m2 = 0, m2f;
  Edge *e1, *e2;
  for (Edge *e = header[i]; e; e = e->next)
    if (e->v != parent)
    {
      const int d = diameter(e->v, i) + e->w;
      if (d > m1)
        m2 = m1, m1 = d,
        m2f = fm[i], fm[i] = e->v,
        e2 = e1, e1 = e;
      else if (d > m2)
        e2 = e, m2f = e->v, m2 = d;
    }
  if (m1+m2 > max)
  {
    max = m1+m2;
    em1 = e1, em2 = e2;
    fm1 = fm[i], fm2 = m2f;
  }
  return m1;
}
void flip(const int i)
{
  for (Edge* e = header[i]; e; e = e->next)
    if (e->v == fm[i])
    {
      e->w = -1;
      flip(e->v);
    }
}
int main()
{
  memset(fm, 255, sizeof(fm));
 
  scanf("%d %d", &n, &m);
  for (int i = 0, x, y; i < n-1; ++i)
  {
    scanf("%d%d", &x, &y);
    add_edge(--x, --y);
    add_edge(y, x);
  }
  diameter(0);
  const int ans1 = max;
  if (m == 1)
    printf("%d", 2*(n-1)-ans1+1);
  else
  {
    max = 0;
    em1->w = -1;
    em2->w = -1;
    flip(fm1);
    flip(fm2);
    diameter(0);
    printf("%d", 2*(n-1)-ans1-max+2);
  }
}

Comments