QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#878998 | #9696. Analysis | ucup-team5177# | WA | 1ms | 10068kb | C++23 | 1.2kb | 2025-02-01 19:38:32 | 2025-02-01 19:38:43 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 19:38:32]
- Submitted
answer
#include <bits/stdc++.h>
#define LL long long
#define INF_LL (0x3f3f3f3f3f3f3f3f)
LL f[500009][2],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]][0]+A,b+f[to[i]][1]+A-B);
LL d=std::max(std::max(0ll,a)+f[to[i]][1]+A,b+f[to[i]][0]+A);
a=std::max(a,c);
b=std::max(b,d);
}
as=std::max(as,a);
as=std::max(as,b-B);
a=std::max(a,b-B);
b=std::max(b,0ll);
b=std::max(b,a);
f[n][0]=a;
f[n][1]=b;
}
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);
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: 100
Accepted
time: 0ms
memory: 10068kb
input:
5 100 1000 1 2 2 3 3 4 4 5
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 10068kb
input:
5 100 200 1 2 1 3 2 4 2 5
output:
0
result:
wrong answer 1st numbers differ - expected: '100', found: '0'