Sonya and Ice Cream(树的直径+单调队列)

描述

传送门:Codeforces Round #495 (Div. 2) - Problem E

Sonya likes ice cream very much. She eats it even during programming competitions. That is why the girl decided that she wants to open her own ice cream shops.

Sonya lives in a city with $n$ junctions and $n - 1$ streets between them. All streets are two-way and connect two junctions. It is possible to travel from any junction to any other using one or more streets. City Hall allows opening shops only on junctions. The girl cannot open shops in the middle of streets.

Sonya has exactly $k$ friends whom she can trust. If she opens a shop, one of her friends has to work there and not to allow anybody to eat an ice cream not paying for it. Since Sonya does not want to skip an important competition, she will not work in shops personally.

Sonya wants all her ice cream shops to form a simple path of the length $r$ ($1 \le r \le k$) , i.e. to be located in different junctions $f_1, f_2, \dots, f_r$ and there is street between $f_i$ and $f_{i+1}$ for each $1$ to $r - 1$.

The girl takes care of potential buyers, so she also wants to minimize the maximum distance between the junctions to the nearest ice cream shop. The distance between two junctions $a$ and $b$ is equal to the sum of all the street lengths that you need to pass to get from the junction $a$ to the junction $b$. So Sonya wants to minimize
$$\max_{a} \min_{1 \le i \le r} d_{a,f_i}$$
where $a$ takes a value of all possible $n$ junctions, $f_i$ — the junction where the $i$-th Sonya’s shop is located, and $d_{x,y}$ — the distance between the junctions $x$ and $y$.

Sonya is not sure that she can find the optimal shops locations, that is why she is asking you to help her to open not more than $k$ shops that will form a simple path and the maximum distance between any junction and the nearest shop would be minimal.

Input

The first line contains two integers $n$ and $k$ ($1\leq k\leq n\leq 10^5$) — the number of junctions and friends respectively.

Each of the next $n - 1$ lines contains three integers $u_i$, $v_i$ and $d_i$($1\leq u_i, v_i\leq n$, $v_i\neq u_i$, $1\leq d\leq 10^4$) — junctions that are connected by a street and the length of this street. It is guaranteed that each pair of junctions is connected by at most one street. It is guaranteed that you can get from any junctions to any other.

Output

Print one number — the minimal possible maximum distance that you need to pass to get from any junction to the nearest ice cream shop. Sonya’s shops must form a simple path and the number of shops must be at most $k$.

Examples

Input Output
1
2
3
4
5
6
6 2
1 2 3
2 3 4
4 5 2
4 6 3
2 4 6
1
4
1
2
3
4
5
6
7
8
9
10
10 3
1 2 5
5 7 2
3 2 6
10 6 3
3 8 1
6 4 2
4 1 6
6 9 4
5 2 5
1
7

Note

In the first example, you can choose the path 2-4, so the answer will be 4.
The first example.

In the second example, you can choose the path 4-1-2, so the answer will be 7.
The second example.

思路

  • 可以用反证法证明,这样一条链一定在直径上。
  • 只需要两遍DFS求出直径,然后在直径上选一段长为$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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;

#pragma optimize("-O3")

typedef long long ll;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

void go();

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
go();
return 0;
}

/****************************************************************************************************/

const int INF = 0x3f3f3f3f;

void go()
{
int n, k;
cin >> n >> k;
vector<vector<PII>> G(n + 1);
for (int i = 1, u, v, w; i < n; i++)
{
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}

VI fa(n + 1), dis(n + 1), vis(n + 1);
int max_dis = 0;

function<void(int, int)> dfs = [&](int u, int f) {
fa[u] = f;
max_dis = max(max_dis, dis[u]);
for (auto& e : G[u])
{
int &v = e.first, &w = e.second;
if (v == f || vis[v]) continue;
dis[v] = dis[u] + w;
dfs(v, u);
}
};

int s = 1;
dfs(s, dis[s] = 0);
for (int i = 1; i <= n; i++)
if (dis[i] > dis[s]) s = i;
dfs(s, dis[s] = 0);
for (int i = 1; i <= n; i++)
if (dis[i] > dis[s]) s = i;

VI t, len, dep;

for (int i = s; i; i = fa[i])
{
t.push_back(i);
len.push_back(dis[i]);
vis[i] = 1;
}

reverse(t.begin(), t.end());
reverse(len.begin(), len.end());

int d = t.size();
k = min(k, d);
for (auto& u : t)
{
dis[u] = max_dis = 0;
dfs(u, 0);
dep.push_back(max_dis);
}

int ans = INF;
deque<PII> q;
for (int i = 0, j = 0; i + k <= d; i++)
{
while (j < i + k)
{
while (!q.empty() && q.back().first < dep[j]) q.pop_back();
q.push_back({dep[j], j}), j++;
}
while (q.front().second < i) q.pop_front();
ans = min(ans, max({len[i], len.back() - len[i + k - 1], q.front().first}));
}
cout << ans << endl;
}
捐助作者
0%