QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#879005 | #9696. Analysis | ucup-team5177# | WA | 0ms | 8016kb | C++23 | 1.2kb | 2025-02-01 19:43:04 | 2025-02-01 19:43:15 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 19:43:04]
- Submitted
answer
#include <bits/stdc++.h>
#define LL long long
#define INF_LL (0x3f3f3f3f3f3f3f3f)
LL f[500009],as=-INF_LL;
int N,A,B,dg[500009],hd[500009],to[1000009],nxt[1000009],k;
void l(int u,int v) {
to[++k]=v;nxt[k]=hd[u];hd[u]=k;
}
void dfs(int n,int ff) {
LL a=-INF_LL,b=-INF_LL,xx=-INF_LL,yy=-INF_LL;
for(int i=hd[n];i;i=nxt[i]) {
if(to[i]==ff) continue;
dfs(to[i],n);
LL c=std::max(std::max(0ll,a)+f[to[i]]+A,b+f[to[i]]+A-B);
LL d=std::max(std::max(0ll,a)+f[to[i]]+A,b+f[to[i]]+A);
a=std::max(a,c);
b=std::max(b,d);
}
b=std::max(b,0ll);
f[n]=std::max(a,b-B);
as=std::max(as,f[n]);
//if(as==200) printf("%d\n",n);
}
signed main(void) {
scanf("%d %d %d",&N,&A,&B);
if(N<=2) {
printf("0");
return 0;
}
for(int i=1;i<N;i++) {
int x,y;
scanf("%d %d",&x,&y);
l(x,y);
l(y,x);
dg[x]++;
dg[y]++;
}
int rt=4742848%N+1;
// for(int i=1;i<=N;i++) {
// if(dg[i]>=2) {
// rt=i;
// break;
// }
// }
dfs(rt,0);
// printf("%d %lld\n",rt,f[4][0]);
LL ans=1ll*A*(N-1)-B-as;
printf("%lld",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 8016kb
input:
5 100 1000 1 2 2 3 3 4 4 5
output:
100
result:
wrong answer 1st numbers differ - expected: '0', found: '100'