POJ 1741

发表于 |

题目

给$N$个点的树。问：有多少点对$(v,w)$的最短距离不超过$K$。

数据范围

$N \leq 10000 \quad \quad K \leq 10000000$

做法

树上的点分治。

按树的重心分解可以使分解后的子树的最大点数不超过原来点数的一半，所以分治的层数有保障，为$O(log_2N)$。

重心分解之后，符合条件的点对$(v,w)$有三种情况：

  1. v和w在同一个子树内。
  2. v和w在不同的子树内。
  3. v和w中一个是重心s，一个不是重心s。

img

其中，情况3可以通过添加一个虚拟的到s的距离为0的点来转化为情况2一起计算。

直接计算情况2不太好算，可以转化为计算：所有满足条件的点对个数-情况1的个数。

为了计算满足条件的点对的个数，每个子问题用了一次排序，由主定理，复杂度为$O(N\times log_2^2N)$

代码

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
118
119
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const int MAX_N = 1e4 + 5;
struct Edge {int to, cost;};
int N, K;
vector<Edge> G[MAX_N];
bool centroid[MAX_N];
int subtreeSize[MAX_N];
int ans;
int computeSubtreeSize(int v, int p)
{
  int c = 1;
  for (int i = 0; i < (int)G[v].size(); ++i) {
    Edge &e = G[v][i];
    if (e.to == p || centroid[e.to]) continue;
    c += computeSubtreeSize(e.to, v);
  }
  return subtreeSize[v] = c;
}
pair<int, int> searchCentroid(int v, int p, int t)
{
  pair<int, int> res = make_pair(INT_MAX, -1);
  int s = 1, m = 0;
  for (int i = 0; i < (int)G[v].size(); ++i) {
    Edge &e = G[v][i];
    if (e.to == p || centroid[e.to]) continue;
    res = min(res, searchCentroid(e.to, v, t));
    m = max(m, subtreeSize[e.to]);
    s += subtreeSize[e.to];
  }
  m = max(m, t - s);
  res = min(res, make_pair(m, v));
  return res;
}
void getDistince(int v, int p, int d, vector<int> &ds)
{
  ds.push_back(d);
  for (int i = 0; i < (int)G[v].size(); ++i) {
    Edge &e = G[v][i];
    if (e.to == p || centroid[e.to]) continue;
    getDistince(e.to, v, d + e.cost, ds);
  }
}
int countPairs(vector<int> &ds)
{
  int res = 0;
  sort(ds.begin(), ds.end());
  for (int l = 0, r = ds.size() - 1; l < r;) {
    if (ds[l] + ds[r] <= K) {
      res += r - l;
      ++l;
    } else {
      --r;
    }
  }
  return res;
}
void solveSubproblem(int v)
{
  computeSubtreeSize(v, -1);
  int s = searchCentroid(v, -1, subtreeSize[v]).second;
  centroid[s] = true;
  for (int i = 0; i < (int)G[s].size(); ++i) {
    Edge &e = G[s][i];
    if (centroid[e.to]) continue;
    solveSubproblem(e.to);
  }
  vector<int> ds;
  ds.push_back(0);
  for (int i = 0; i < (int)G[s].size(); ++i) {
    Edge &e = G[s][i];
    if (centroid[e.to]) continue;
    vector<int> tds;
    getDistince(e.to, s, e.cost, tds);
    ans -= countPairs(tds);
    ds.insert(ds.end(), tds.begin(), tds.end());
  }
  ans += countPairs(ds);
  centroid[s] = false;
}
void solve()
{
  ans = 0;
  solveSubproblem(0);
  printf("%d\n", ans);
}
void addEdge(int a, int b, int c)
{
  G[a].push_back((Edge){b, c});
  G[b].push_back((Edge){a, c});
}
int main()
{
  while (scanf("%d%d", &N, &K), N) {
    for (int i = 0; i < N; ++i) G[i].clear();
    for (int i = 1; i < N; ++i) {
      int a, b, c; scanf("%d%d%d", &a, &b, &c); --a; --b;
      addEdge(a, b, c);
    }
    solve();
  }
  return 0;
}

总结

分治法的思想：分解、解决、合并。在合并的时候，子问题已经解决了。分解一般二分，树上的话重心分解。