[BZOJ2599][IOI2011]Race

题目很简短：给定一棵树，边有权，求一条路径使得边权和等于K，且边数最少。第一次做树分治，Orz cxjyxx_me。

点分治大体思路

对于一个有根图的某个点，它的状态只有两种：

  • 不在答案的路径上。这个时候就要递归处理它的所有子树，取一个最优答案。
  • 在答案的路径上。

在答案的路径上的话，也有两种状态（不是每个题目都需要分开考虑）：

  • 这个点在答案的链的一端。可以DFS。
  • 这个点在答案的链的中间。可以DFS每棵子树，然后合并两条链。

有意思的是，这个看似暴力的分治，在每次选取重心的时候，可以证明有O(nlogn)的复杂度。所谓重心，就是以它为根的树中最大子树最小的那个点。实际做的时候并不需要每次都换根，只需要以任意点开始做，算出这样形态下每个节点的大小，这样，换到以i为根的时候，只要多出一个n-son[i] (n为节点总数)的子树即可。

这题的做法

因为K不是很大，所以可以开个桶记下来所有子树出现过的边权和，这样如果一个答案是T，那么我们只要考虑K-T即可。但是需要注意一个问题：我们并不希望出现两条链都在同一棵子树上的情况，所以我们在做DP的时候，要先更新答案，在更新用来统计边权的桶。

用dist[u].first表示到达u点的路径长度，dist[u].second表示到达u的边数。m[k].first表示k这个边权最少需要几条边可以走到，m[k].second作为时间戳，用来区别递归时的不同子树。

代码

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
106
107
108
109
110
111
112
113
114
115
116
117

#include <queue>
#include <stack>
#include <cstdio>
#include <algorithm>

const int MAXN = 200001, MAXK = 2000001;
typedef std::pair<int, int> Pair;
struct Edge
{
  int v, w;
  Edge *next;
} g[MAXN*2], *header[MAXN];
void AddEdge(const int x, const int y, const int w)
{
  static int LinkSize;
  Edge* const node = g+(LinkSize++);
  node->v = y;
  node->w = w;
  node->next = header[x];
  header[x] = node;
}
int n, K, parent[MAXN], ans = 0x3F3F3F3F;
bool mark[MAXN];
std::queue<int> q;
int getcore(const int root)
{
  static int son[MAXN];
  static std::stack<int> s;
  int nodes = 0;
  for (q.push(root), parent[root] = -1; !q.empty(); q.pop())
  {
    const int u = q.front();
    s.push(u);
    ++nodes;
    for (Edge *e = header[u]; e; e = e->next)
      if (!mark[e->v] && e->v != parent[u])
      {
        parent[e->v] = u;
        q.push(e->v);
      }
  }
  int core = 0x3F3F3F3F, m = 0x3F3F3F3F;
  for (; !s.empty(); s.pop())
  {
    const int u = s.top();
    int maxson = 0, cnt = 0;
    for (Edge *e = header[u]; e; e = e->next)
      if (!mark[e->v] && e->v != parent[u])
      {
        cnt += son[e->v];
        maxson = std::max(maxson, son[e->v]);
      }
    maxson = std::max(maxson, nodes-(son[u] = cnt+1));
    if (maxson < m)
      m = maxson, core = u;
  }
  return core;
}
void solve(const int core)
{
  static int timestamp;
  static Pair dist[MAXN], m[MAXK];
  mark[core] = true;
  m[0].first = 0, m[0].second = ++timestamp;
  for (Edge *edge = header[core]; edge; edge = edge->next)
  {
    const int st = edge->v;
    if (mark[st]) continue;
    for (q.push(st), dist[st].first = edge->w, dist[st].second = 1, parent[st] = -1; !q.empty(); q.pop())
    {
      const int u = q.front();
      if (dist[u].first <= K && m[K-dist[u].first].second == timestamp)
        ans = std::min(ans, dist[u].second + m[K-dist[u].first].first);
      for (Edge *e = header[u]; e; e = e->next)
      {
        if (mark[e->v] || parent[u] == e->v) continue;
        parent[e->v] = u;
        dist[e->v].first = dist[u].first + e->w;
        dist[e->v].second = dist[u].second + 1;
        q.push(e->v);
      }
    }
    for (q.push(st); !q.empty(); q.pop())
    {
      const int u = q.front();
      if (dist[u].first <= K && (m[dist[u].first].second != timestamp || dist[u].second < m[dist[u].first].first))
      {
        m[dist[u].first].first = dist[u].second;
        m[dist[u].first].second = timestamp;
      }
      for (Edge *e = header[u]; e; e = e->next)
        if (!mark[e->v] && parent[u] != e->v)
          q.push(e->v);
    }
  }
}
int main()
{
  scanf("%d%d", &n, &K);
  for (int i = 1, x, y, w; i < n; ++i)
  {
    scanf("%d%d%d", &x, &y, &w);
    AddEdge(++x, ++y, w);
    AddEdge(y, x, w);
  }
  std::queue<int> Q;
  for (Q.push(1); !Q.empty(); Q.pop())
  {
    const int u = Q.front();
    const int core = getcore(u);
    solve(core);
    for (Edge *e = header[core]; e; e = e->next)
      if (!mark[e->v])
        Q.push(e->v);
  }
  printf("%d", ans == 0x3F3F3F3F ? -1 : ans);
}

Comments