QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#878980 | #9696. Analysis | ucup-team5177# | WA | 1ms | 10068kb | C++23 | 1.2kb | 2025-02-01 19:30:31 | 2025-02-01 19:30:31 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 19:30:31]
- 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);
b=std::max(b,0ll);
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=0;
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);
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 10064kb
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: 10064kb
input:
5 100 200 1 2 1 3 2 4 2 5
output:
100
result:
ok 1 number(s): "100"
Test #3:
score: 0
Accepted
time: 0ms
memory: 10068kb
input:
10 133494816 109943166 10 8 5 3 1 2 8 9 8 5 2 4 8 7 8 6 10 1
output:
219886332
result:
ok 1 number(s): "219886332"
Test #4:
score: 0
Accepted
time: 0ms
memory: 10064kb
input:
10 165074331 854297934 6 2 2 7 9 8 2 9 9 10 6 3 6 4 5 6 6 1
output:
825371655
result:
ok 1 number(s): "825371655"
Test #5:
score: 0
Accepted
time: 0ms
memory: 10068kb
input:
9 719441223 227056392 4 6 9 2 5 3 1 4 6 8 1 9 1 7 3 1
output:
227056392
result:
ok 1 number(s): "227056392"
Test #6:
score: 0
Accepted
time: 0ms
memory: 10036kb
input:
10 216399993 137522662 9 6 1 2 2 9 4 1 10 3 7 5 5 4 3 7 2 8
output:
137522662
result:
ok 1 number(s): "137522662"
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 10064kb
input:
10 796722415 144928611 9 10 6 4 2 7 5 1 3 2 6 5 3 9 1 8 6 3
output:
144928611
result:
wrong answer 1st numbers differ - expected: '289857222', found: '144928611'