QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#878248#9696. Analysisucup-team5234#WA 1ms3584kbC++231.9kb2025-02-01 14:21:332025-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:37]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3584kb
  • [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;
}

詳細信息

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'