#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), b(n), c(n);
for (int i = 0; i < n - 1; ++i) {
cin >> a[i] >> b[i] >> c[i];
--a[i];
--b[i];
}
int ans = 0;
vector<pair<int, int>> pairs;
function<void()> go = [&]() {
vector<int> cnt_center(n, 0);
for (auto p : pairs) {
int i = p.first, j = p.second;
map<int, int> mp;
++mp[a[i]]; ++mp[b[i]];
++mp[a[j]]; ++mp[b[j]];
for (auto [v, cnt] : mp) {
if (cnt >= 2) ++cnt_center[v];
}
}
bool ok = 1;
for (int i = 0; i < n; ++i) ok &= cnt_center[i] <= 1;
if (ok) {
int cur_ans = 0;
vector<bool> used(n, 0);
for (auto p : pairs) {
used[p.first] = used[p.second] = 1;
cur_ans += c[p.first];
cur_ans += c[p.second];
}
ans = max(ans, cur_ans);
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
map<int, int> mp;
++mp[a[i]]; ++mp[b[i]];
++mp[a[j]]; ++mp[b[j]];
bool can = 0;
for (auto [v, cnt] : mp) {
if (cnt >= 2) can = 1;
}
if (can && !used[i] && !used[j]) {
pairs.push_back({i, j});
go();
pairs.pop_back();
}
}
}
}
};
go();
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
364 KB |
Output is correct |
3 |
Correct |
3 ms |
364 KB |
Output is correct |
4 |
Correct |
3 ms |
364 KB |
Output is correct |
5 |
Correct |
3 ms |
364 KB |
Output is correct |
6 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
364 KB |
Output is correct |
3 |
Correct |
3 ms |
364 KB |
Output is correct |
4 |
Correct |
3 ms |
364 KB |
Output is correct |
5 |
Correct |
3 ms |
364 KB |
Output is correct |
6 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
364 KB |
Output is correct |
3 |
Correct |
3 ms |
364 KB |
Output is correct |
4 |
Correct |
3 ms |
364 KB |
Output is correct |
5 |
Correct |
3 ms |
364 KB |
Output is correct |
6 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
364 KB |
Output is correct |
3 |
Correct |
3 ms |
364 KB |
Output is correct |
4 |
Correct |
3 ms |
364 KB |
Output is correct |
5 |
Correct |
3 ms |
364 KB |
Output is correct |
6 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |