QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#879257#9696. Analysisucup-team1766#WA 0ms5856kbC++173.0kb2025-02-01 23:01:182025-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:28]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 5856kb
  • [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'