QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#888846 | #9696. Analysis | njuprac# | WA | 4ms | 29104kb | C++14 | 1.5kb | 2025-02-08 13:17:20 | 2025-02-08 13:17:26 |
Judging History
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'