TIOJ-1838

發表於 更新於 Disqus：

給一座邊上帶權$T_i$的森林，加邊權為$l$邊把他們連成一棵樹，輸出最短樹直徑。

$N\le 10^5, 0\le M < n,1\le T_i, l\le 10^4$

*第二道靠自己寫出的IOI題目>////<*
先考慮圖上無任何邊(也就是只有$N$個點)的時候，最佳解應該是把他們連成這樣：

star
這樣樹直徑只會是$2l$，沒辦法再更少了。

然後在考慮森林中的每棵樹，最佳解會是找出樹上某個點當根，並且以他當根的最大深度最小。(後來知道那叫圓心)找出那個點可以用樹dp做到，考慮以i為根最大深度，轉移時就把從父節點那一條給拉過來就好。
然後把根與根相接，接成上面的形狀，至於中間的點我們就選用最大深度最大的那棵樹。
可能會有三個case:

  1. 本來某棵的樹直徑就已經最大
  2. 最大深度第二深的樹連到中間那個
  3. 第二大深度的樹連到第三大深度的樹

這樣答案就會是$max($每棵樹的直徑$, $最大深度的樹$+l+$第二大深度的樹$, $第二大深度的樹$+2l+$第三大深度的樹$)$。

時間複雜度$\mathcal{O}(nlogn)$

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
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
/*-----------------------------------------------------------------------------------------------------*/

vector<vector<pair<int, int>>> edge;
vector<int> ans, dep;
vector<int> cur;

void dfs(int v, int p) {
	for(auto a : edge[v]) {
		if(a.first == p)
			continue;
		dfs(a.first, v);
		dep[v] = max(dep[v], dep[a.first] + a.second);
	}
}
void dfs(int v, int p, int w) {
	multiset<int> des;
	ans[v] = max(dep[v], w);
	cur.push_back(ans[v]);
	for(auto &[a, b] : edge[v])
		if(a != p)
			des.insert(dep[a] + b);
	for(auto &[a, b] : edge[v]) {
		if(a == p)
			continue;
		des.erase(des.find(dep[a] + b));
		dfs(a, v, max(w, des.size() ? *des.rbegin() : 0) + b);
		des.insert(dep[a] + b);
	}
}

void solve(int n, int m, int l) {
	int lans = 0;
	edge.clear(); edge.resize(n);
	ans.clear(); ans.resize(n);
	dep.clear(); dep.resize(n);
	vector<int> owo;
	for(int i = 0, a, b, c; i < m; i++)
		cin >> a >> b >> c, edge[a].push_back({b, c}), edge[b].push_back({a, c});
	for(int i = 0; i < n; i++) {
		if(ans[i])
			continue;
		dfs(i, i);
		dfs(i, i, 0);
		lans = max(lans, *max_element(cur.begin(), cur.end()));
		owo.push_back(*min_element(cur.begin(), cur.end()));
		cur.clear();
	}
	sort(owo.begin(), owo.end(), greater<int>());
	if(owo.size() > 1)
		lans = max(lans, owo[0] + owo[1] + l);
	if(owo.size() > 2)
		lans = max(lans, owo[1] + owo[2] + 2 * l);
	cout << lans << '\n';
}

signed main() {
	EmiliaMyWife

	int n, m, l;
	while(cin >> n >> m >> l)
		solve(n, m, l);

	return 0;
}