题目#

公元 $2044$ 年，人类进入了宇宙纪元。

L 国有 $n$ 个星球，还有 $n-1$ 条双向航道，每条航道建立在两个星球之间，这 $n-1$ 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 $u_i$ 号星球沿最快的宇航路径飞行到 $v_i$ 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 $j$ ，任意飞船驶过它所花费的时间为 $t_j$ ，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 $m$ 个运输计划。在虫洞建设完成后，这 $m$ 个运输计划会同时开始，所有飞船一起出发。当这 $m$ 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞，试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？对于 $100\%$ 的数据，保证： $1 \leq a_i,b_i \leq n$ ， $0 \leq t_i \leq 1000$ ， $1 \leq u_i,v_i \leq n$ 。

题解#

首先提炼出题目要求——最大值最小想到二分最大值想一想二分之后如何判断是否合法把大于最大值的路径都选出来，在树上标记出来如果有一个边被选出来的所有路径都包括，且这其中最长的路径减去边权小于二分值，那么就合法，否则就不

实现问题#

把大于最大值的路径都选出来

路径长度可以用树上前缀和

把大于最大值的路径都选出来，在树上标记出来

树上差分

出现的问题

1.二分写错 2.要用upper_bound 3.二分测试没全部初始化

AC代码#

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N = 3e5 + 100;
4
int head[N], nxt[N << 1], edge[N << 1], to[N << 1], cnt = 1;
5

6
int point_to_edge[N];
7

8
int n, m;
9

10
int longest_path;
11
struct U
12
{
13
  int m, n, length;
14

15
  bool operator < (const U o) const
16
  {
17
    return length < o.length;
18
  }
19
} u[N];
20

21

22
// <lca>
23

24
int anc[N][21], depth[N];
25

26
void lca_init()
27
{
28
  for(int j = 1; j <= 20;j++)
29
  {
30
    for(int i = 1;i <= n;i++)
31
    {
32
      anc[i][j] = anc[anc[i][j - 1]][j - 1];
33
    }
34
  }
35
}
36

37
int lca_query(int x, int y)
38
{
39
  if(depth[x] < depth[y])
40
    swap(x, y);
41

42

43

44
  for(int j = 20;j >= 0;j--)
45
  {
46
    if(depth[anc[x][j]] >= depth[y])
47
    {
48
      x = anc[x][j];
49
    }
50
  }
51

52
  if(x == y) return x;
53
  for(int j = 20;j >= 0;j--)
54
  {
55
    if(anc[x][j] != anc[y][j])
56
    {
57
      x = anc[x][j], y = anc[y][j];
58
    }
59
  }
60
  return anc[x][0];
61
}
62
// </lca>
63

64
// <预处理前缀和+lca>
65

66
int sum[N];
67
void dfs_sum(int u, int fa)
68
{
69
  depth[u] = depth[fa] + 1;
70
  anc[u][0] = fa;
71
  for(int i = head[u]; i; i = nxt[i])
72
  {
73
    int v = to[i];
74
    if(v == fa) continue;
75
    point_to_edge[v] = i;
76
    sum[v] = sum[u] + edge[i];
77
    dfs_sum(v, u);
78
  }
79
}
80

81
// </预处理前缀和>
82

83

84
// <快读>
85
int read()
86
{
87
  int f = 1, x = 0;
88
  char ch = getchar();
89
  while(ch < '0' || ch > '9')
90
  {
91
    if(ch == '-') f = -1;
92
    ch = getchar();
93
  }
94

95
  while(ch >= '0' && ch <= '9')
96
  {
97
    x = x * 10 + ch - '0';
98
    ch = getchar();
99
  }
100
  return f * x;
101
}
102

103
// </快读>
104

105

106

107
void add(int x, int y, int z)
108
{
109
  to[++cnt] = y;
110
  edge[cnt] = z;
111
  nxt[cnt] = head[x];
112
  head[x] = cnt;
113
}
114

115
// <check>
116

117
// <树上差分>
118

119
int differ[N], sum_differ[N];
120
int best_can_edge_quan = 0;
121

122

123
void dfs_differ(int u, int fa, int T)
124
{
125
  sum_differ[u] += differ[u];
126
  for(int i = head[u]; i; i = nxt[i])
127
  {
128
    int v = to[i];
129
    if(v == fa) continue;
130
    dfs_differ(v, u, T);
131
    sum_differ[u] += sum_differ[v];
132
  }
133
  if(sum_differ[u] == (m - T + 1) && best_can_edge_quan < edge[point_to_edge[u]])
134
  {
135
    best_can_edge_quan = edge[point_to_edge[u]];
136
  }
137

138
//  cout << "qwq "<<u <<" "<< sum_differ[u] << endl;
139
}
140

141
// </树上差分>
142

143
bool check(int T)
144
{
145
  best_can_edge_quan = 0;
146
  memset(differ, 0, sizeof(differ));
147
  memset(sum_differ, 0, sizeof(sum_differ));
148

149

150
  U temp;
151
  temp.m = temp.n = 0;
152
  temp.length = T;
153
  int first_bad_order = upper_bound(u + 1, u + 1 + m/*!!!*/, temp) - u;
154
  if(temp.length >= u[first_bad_order].length && first_bad_order == m) return 1;
155

156
//  cout << "qwq"<<first_bad_order << endl;
157
//  cout << first_bad_order << endl;
158
  for(int i = first_bad_order;i <= m;i++)
159
  {
160
    differ[u[i].m]++, differ[u[i].n]++, differ[lca_query(u[i].n, u[i].m)] -= 2;
161
  }
162

163
  dfs_differ(1, 0, first_bad_order);
164

165

166
//  cout << "qwq" << best_can_edge_quan << endl;
167
  if(longest_path - best_can_edge_quan <= T)
168
  {
169
    return 1;
170
  }
171
  return 0;
172
}
173

174
// </check>
175

176

177
int binary_search(int r)
178
{
179
  int l = 0;
180

181
  while(l < r)
182
  {
183
    int mid = (l + r) >> 1;
184
//    cout << mid << endl;
185
    if(check(mid)/*可行*/)
186
    {
187
      r = mid;
188
//      cout << mid << " ok" << endl;
189
    }
190
    else
191
    {
192
      l = mid + 1;
193
//      cout << mid << " n" << endl;
194
    }
195
  }
196
  return l;
197
}
198

199
int main()
200
{
201
  n = read(), m = read();
202

203
  int x, y, z;
204
  for(int i = 1;i <= n - 1;i++)
205
  {
206
    x = read(), y = read(), z = read();
207
    add(x, y, z), add(y, x, z);
208
  }
209
  dfs_sum(1, 0);
210
  lca_init();
211

212

213

214
  for(int i = 1;i <= m;i++)
215
  {
216
    u[i].m = read(), u[i].n = read(), u[i].length = sum[u[i].n] + sum[u[i].m] - 2 * sum[lca_query(u[i].n, u[i].m)];
217
    longest_path = max(longest_path, u[i].length);
218
  }
219

220
  sort(u + 1, u + 1 + m);
221

222
  printf("%d\n", binary_search(longest_path));
223

224
//  differ[2] ++, differ[6] ++, differ[4] ++,differ[1] -= 2;
225
//
226
//  dfs_differ(1, 0, 0);
227
//  cout << sum_differ[1];
228
//  cout << edge[point_to_edge[3]];
229
  return 0;
230
}