QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#879257 | #9696. Analysis | ucup-team1766# | WA | 0ms | 5856kb | C++17 | 3.0kb | 2025-02-01 23:01:18 | 2025-02-01 23:01:28 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 23:01:18]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int height[MAXN];
long long dp[MAXN];
int n;
long long A, B, res;
void dfs1(vector<vector<int>> &tree, int cur, int par) {
int max_height = -1;
for (int nei : tree[cur]) {
if (nei != par) {
dfs1(tree, nei, cur);
if (max_height == -1 || height[nei] > height[max_height]) {
max_height = nei;
}
}
}
height[cur] = (max_height == -1 ? 0 : height[max_height] + 1);
dp[cur] = 0;
for (int nei : tree[cur]) {
if (nei != par) {
dp[cur] += dp[nei];
if (nei != max_height) {
dp[cur] += min(B, (height[nei] + 1) * A);
}
}
}
}
void dfs2(vector<vector<int>> &tree, int par_height, int cur, int par) {
int prev_cur = dp[cur];
vector<pair<int, int>> by_height;
if (par != -1) {
by_height.emplace_back(par_height, par);
}
for (int nei : tree[cur]) {
if (nei != par) {
by_height.emplace_back(height[nei], nei);
}
}
sort(by_height.begin(), by_height.end());
dp[cur] = 0;
for (int nei : tree[cur]) {
if (nei != par) {
dp[cur] += dp[nei];
if (nei != by_height.back().second) {
dp[cur] += min(B, (height[nei] + 1) * A);
}
}
}
if (par != -1) {
dp[cur] += dp[par];
if (par != by_height.back().second) {
dp[cur] += min(B, (par_height + 1) * A);
}
}
res = min(res, dp[cur]);
for (int nei : tree[cur]) {
if (nei != par) {
dp[cur] -= dp[nei];
if (nei == by_height.back().second) {
int next_height = max(par_height + 1,
(by_height.size() >= 2 ? by_height[by_height.size() - 2].first : 0) + 1);
int add = 0;
if (by_height.size() >= 2) {
int new_max = by_height[by_height.size() - 2].first;
add = min(B, (new_max + 1) * A);
dp[cur] -= add;
}
dfs2(tree, next_height, nei, cur);
dp[cur] += add;
} else {
int next_height = max(par_height + 1, by_height.back().first + 1);
dp[cur] -= min(B, (height[nei] + 1) * A);
dfs2(tree, next_height, nei, cur);
dp[cur] += min(B, (height[nei] + 1) * A);
}
dp[cur] += dp[nei];
}
}
dp[cur] = prev_cur;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> A >> B;
vector<vector<int>> tree(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs1(tree, 0, -1);
res = LONG_LONG_MAX;
dfs2(tree, -1, 0, -1);
cout << res << "\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5856kb
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: 5856kb
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: 5724kb
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'