QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#878336 | #9696. Analysis | ucup-team3802# | WA | 1ms | 3584kb | C++23 | 1.6kb | 2025-02-01 14:50:00 | 2025-02-01 14:50:00 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 14:50:00]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, l, r) for(ll i = l; i < r; i++)
#define all(ar) begin(ar), end(ar)
void chmin(ll &a, ll b) { a = min(a, b); }
void solve() {
ll n, a, b;
cin >> n >> a >> b;
vector<vector<int>> g(n);
rep(i, 0, n - 1) {
ll u, v;
cin >> u >> v;
u--;
v--;
g[u].push_back(v);
g[v].push_back(u);
}
auto dfs = [&](auto self, ll v, ll p) -> pair<ll, ll> {
vector<pair<ll, ll>> ch;
for(int u : g[v]) {
if(u != p) {
ch.push_back(self(self, u, v));
}
}
if(ch.empty()) return {0, 0};
for(auto &[f, s] : ch) {
s += a;
}
sort(all(ch), [&](pair<ll, ll> p1, pair<ll, ll> p2) {
return p1.second - p1.first < p2.second - p2.first;
});
vector<ll> res(2, 1LL << 60);
ll s1 = 0;
for(auto [f, s] : ch) s1 += f;
res[(ch.size() + 1) % 2] = s1 + (ch.size() / 2) * b;
rep(i, 0, ch.size()) {
s1 -= ch[i].first;
s1 += ch[i].second;
chmin(res[(ch.size() - i) % 2], s1 + ((ch.size() - i - 1) / 2) * b);
}
// cout << v + 1 << " " << res[0] << " " << res[1] << endl;
return {res[0], res[1]};
};
int r = 0;
while(g[r].size() > 1) r++;
auto [f, s] = dfs(dfs, r, -1);
cout << f << endl;
}
int main() {
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
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: 3584kb
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:
243437982
result:
wrong answer 1st numbers differ - expected: '219886332', found: '243437982'