QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#878248 | #9696. Analysis | ucup-team5234# | WA | 1ms | 3584kb | C++23 | 1.9kb | 2025-02-01 14:21:33 | 2025-02-01 14:21:37 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 14:21:33]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i ++)
const ll INF = (1LL << 60);
void chmin(ll &a, ll b) {a = min(a, b);}
#define foa(e, a) for(auto e : a)
#define pb(n) push_back(n)
int main() {
ll n, a, b;
cin >> n >> a >> b;
vector<vector<int>> v(n);
rep(i, n - 1) {
int x, y;
cin >> x >> y;
x --; y --;
v[x].pb(y);
v[y].pb(x);
}
int r = -1, ma = -1;
auto dfs = [&](auto dfs, int now, int p, int dis) -> void {
if(ma < dis) {
ma = dis;
r = now;
}
foa(e, v[now]) {
if(e == p) continue;
dfs(dfs, e, now, dis + 1);
}
};
dfs(dfs, 0, -1, 0);
vector<ll> len(n, 0);
auto dfs2 = [&](auto dfs2, int now, int p) -> ll {
ll ret = 0;
foa(e, v[now]) {
if(e == p) continue;
ret = max(ret, dfs2(dfs2, e, now) + 1);
}
len[now] = ret;
return len[now];
};
dfs2(dfs2, r, -1);
ll ans = 0;
auto dfs1 = [&](auto dfs1, int now, int p, bool flag) -> int {
vector<pair<ll, ll>> vec;
foa(e, v[now]) {
if(e == p) continue;
vec.push_back({len[e], e});
// dfs1(dfs1, e, now);
}
sort(all(vec));
int cnt = vec.size();
ll ma = 1;
foa(e1, vec) {
int e = e1.second;
if(cnt == 1 and flag) {
ll ret = dfs1(dfs1, e, now, 1);
continue;
}
ll ret = dfs1(dfs1, e, now, 0);
cnt --;
if(cnt == 0) {
ma = ret + 1;
continue;
}
ans += min(a * ret, b);
}
return ma;
};
dfs1(dfs1, r, -1, 1);
cout << ans << endl;
return 0;
}
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: 3456kb
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'