QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#888846#9696. Analysisnjuprac#WA 4ms29104kbC++141.5kb2025-02-08 13:17:202025-02-08 13:17:26

Judging History

This is the latest submission verdict.

  • [2025-02-08 13:17:26]
  • Judged
  • Verdict: WA
  • Time: 4ms
  • Memory: 29104kb
  • [2025-02-08 13:17:20]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(x,l,r) for(int x=l;x<=r;x++)
#define per(x,r,l) for(int x=r;x>=l;x--)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()

const int MOD=998244353;
int power(int a,int k,int mod=MOD) {
    k%=mod-1; if(k<0) k+=mod-1;
    int res=1; while(k) {
        if(k&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod,k>>=1;
    } return res;
}

const int N=500500;

int n,a,b;
vector<int> G[N];

int dep[N];
void dfs(int u,int father) {
    dep[u]=dep[father]+1;
    for(int v:G[u]) {
        if(v==father) continue;
        dfs(v,u);
    }
}

int md[N];
vector<int> rec[N];
void dfs2(int u,int father) {
    md[u]=0;
    for(int v:G[u]) {
        if(v==father) continue;
        dfs2(v,u);
        rec[u].pb(md[v]+1);
        md[u]=max(md[u],md[v]+1);
    }
    sort(all(rec[u]));
    if(rec[u].size()) rec[u].pop_back();
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>a>>b;
    rep(i,1,n-1) {
        int u,v; cin>>u>>v;
        G[u].pb(v),G[v].pb(u);
    }
    dfs(1,0);
    int k=0; rep(i,1,n) if(dep[i]>dep[k]) k=i;
    dfs2(k,0);
    // int mx=0; rep(i,1,n) mx=max(mx,dep[i]);
    // rep(i,1,n) cout<<dep[i]<<' '; cout<<'\n';
    // k=n-mx;
    // cout<<1ll*k*min(a,b);
    ll ans=0;
    rep(i,1,n) {
        for(int j:rec[i]) {
            ans+=min((ll)b,1ll*a*j);
        }
    }
    cout<<ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 28976kb

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: 3ms
memory: 28980kb

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: 4ms
memory: 29104kb

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'