QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#881238 | #9696. Analysis | LEFt_bank | WA | 0ms | 3712kb | C++20 | 1.7kb | 2025-02-04 14:00:22 | 2025-02-04 14:00:22 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-04 14:00:22]
- Submitted
answer
#pragma GCC optimize(3, "Ofast", "unroll-loops", "-funroll-loops")
#include<bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;
main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
i32 n;
i64 A, B;
cin >> n >> A >> B;
vector<vector<i32>> ed(n + 1);
for (i32 _ = 1; _ < n; _++) {
i32 u, v;
cin >> u >> v;
ed[u].emplace_back(v);
ed[v].emplace_back(u);
}
vector<i32> dep(n + 1), son(n + 1), mson(n + 1);
i32 rt = -1, md = -1;
auto dfs = [&](auto &&self, i32 u, i32 fa) -> void {
dep[u] = dep[fa] + 1;
if (dep[u] > md) {
rt = u;
md = dep[u];
}
mson[u] = dep[u];
for (i32 v : ed[u]) {
if (v != fa) {
self(self, v, u);
if (mson[v] > mson[u]) {
son[u] = v;
mson[u] = mson[v];
}
}
}
};
dfs(dfs, 1, 1);
fill(son.begin(), son.end(), 0);
dep[rt] = 0;
i32 t = rt;
dfs(dfs, rt, rt);
vector<i64> len;
// for (i32 i = 1; i <= n; i++) {
// cout << son[i] << ' ';
// }
// cout << '\n';
auto tdfs = [&](auto &&self, i32 u, i32 fa, i32 tp) -> void {
if (tp == u) {
len.emplace_back(mson[u] - dep[u] + 1);
}
if (son[u]) {
self(self, son[u], u, tp);
}
for (i32 v : ed[u]) {
if (v != son[u] && v != fa) {
self(self, v, u, v);
}
}
};
// return 0;
tdfs(tdfs, t, t, t);
sort(len.begin(), len.end());
len.pop_back();
i64 ans = 0;
for (auto i : len) {
ans += min(B, i * A);
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
5 100 1000 1 2 2 3 3 4 4 5
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
5 100 200 1 2 1 3 2 4 2 5
output:
100
result:
ok 1 number(s): "100"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3584kb
input:
10 133494816 109943166 10 8 5 3 1 2 8 9 8 5 2 4 8 7 8 6 10 1
output:
329829498
result:
wrong answer 1st numbers differ - expected: '219886332', found: '329829498'