QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#878980#9696. Analysisucup-team5177#WA 1ms10068kbC++231.2kb2025-02-01 19:30:312025-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]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 10068kb
  • [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);
}

Details

Tip: Click on the bar to expand more detailed information

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'