QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497897#6438. CrystalflyRailgun2334WA 29ms11884kbC++204.5kb2024-07-29 20:08:582024-07-29 20:09:00

Judging History

你现在查看的是最新测评结果

  • [2024-07-29 20:09:00]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:11884kb
  • [2024-07-29 20:08:58]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
#define re read()
#define INF 9223372036854775800
#define fr(i, x, y) for(int i = x, p = y; i <= p; ++i) 
#define rp(i, x, y) for(int i = x, p = y; i >= p; --i)
#define Timeok ((double)clock() / CLOCKS_PER_SEC < MAX_TIME)
const double MAX_TIME = 1.0 - 0.0032;

inline ll read()
{
   ll x = 0, f = 0;
   char ch = getchar();
   while (!isdigit(ch))
      f |= (ch == '-'), ch = getchar();
   while (isdigit(ch))
      x = (x << 1) + (x << 3) + (ch ^= 48), ch = getchar();
   return f ? -x : x;
}

void write(ll x)
{
   if (x < 0)
      putchar('-'), x = -x;
   if (x > 9)
      write(x / 10);
   putchar(x % 10 + 48);
}

inline void W(ll x, char ch)
{
    write(x);
    putchar(ch);
}

/*------------C-O-D-E------------*/

const int N = 5e5 + 4;
ll n, m, T;

struct node
{
    ll nxt, to;
} t[N];

ll a[N], k[N];

ll head[N], tot;
ll f[N], fson[N];


void add(ll u, ll v)
{
    t[++tot].nxt = head[u];
    t[tot].to = v;
    head[u] = tot;
}

void C()
{
    fr(i,1,2*n+3) t[i]={0,0},head[i]=0;
    tot=0;
    fr(i,1,2*n+3) f[i] = 0, fson[i] = 0;
    fr(i,1,n+3) a[i]=0,k[i] =0;
}

void dfs(ll now, ll fa)
{
    for(int i = head[now]; i;i = t[i].nxt)
    {
        ll y = t[i].to;
        if(y == fa) continue;
        dfs(y, now);
    }

    ///////
    ll maxn3 = 0, maxson = 0; 
    for(int i = head[now]; i;i = t[i].nxt)
    {
        ll y = t[i].to;
        if(y == fa) continue;
        if(k[y] == 3)
        {
            maxn3 = max(maxn3, a[y]);
        }
        maxson = max(maxson, a[y]);
    }

    if(maxn3 == 0)
    {
        ll sum = maxson;
        for(int i = head[now]; i; i = t[i].nxt)
        {
            ll y = t[i].to;
            if(y == fa) continue;
            sum += f[y];
        }
        f[now] = sum;
        fson[now] = sum - maxson;

        // W(now, ' '); W(f[now], '\n');
    }
    else
    {
        ll sum = maxson;
        for(int i = head[now]; i; i = t[i].nxt)
        {
            ll y = t[i].to;
            if(y == fa) continue;
            sum += f[y];
        }
        f[now] = sum;
        fson[now] = sum - maxson;

        ////////
        sum = 0;
        for(int i = head[now]; i;i = t[i].nxt)
        {
            ll y = t[i].to;
            if(y == fa) continue;
            sum += f[y];
        }

        ll cha = 0, _a = 0;
        ll sumpre = sum;
        // sum += maxn3;
        for(int i = head[now]; i;i = t[i].nxt)
        {
            sum = sumpre;
            cha = 0, _a = 0;
            ll y = t[i].to;
            if(y == fa) continue;
            if(k[y] == 3)
            {
                // okmaxn3 = 1;
                sum += a[y];
                for(int j = head[now]; j;j = t[j].nxt)
                {
                    ll v = t[j].to;
                    if(v == fa) continue;
                    if(v == y) continue;
                    ll nownow = a[v] - (f[v] - fson[v]);
                    // if(k[v] == 3) nownow = a[v];
                    if(cha < nownow)
                    {
                        cha = nownow;
                        _a = a[v];
                    }
                }
                sum += cha;
                if(f[now] < sum)
                {
                    f[now] = sum;
                    fson[now] = f[now] - a[y] - _a;
                }
            }
            // else
            // {
            //     // cha = max(cha, a[y] - (f[y] - fson[y]));
            //     // if(a[y] - (f[y] - fson[y]) < 0) continue;
            //     ll nownow = a[y] - (f[y] - fson[y]);
            //     if(k[y] == 3) nownow = a[y];
            //     if(cha < nownow)
            //     {
            //         cha = nownow;
            //         _a = a[y];
            //     }
            //     // W(cha,'\n');
            // }
        }
        // // if(cha == -1) cha = 0;
        // sum += cha;
        //     // puts("233");

        // if(f[now] < sum)
        // {
        //     f[now] = sum;
        //     fson[now] = f[now] - maxn3 - _a;
        // }
    }
}

void solve()
{
    n = re;
    fr(i,1,n) a[i] = re;
    fr(i,1,n) k[i] = re;
    fr(i,1,n-1)
    {
        ll x = re, y = re;
        add(x,y);
        add(y,x);
    }

    dfs(1, 0);
    W(f[1] + a[1], '\n');

    C();
    return;
}


int main()
{
    ll T = re;
    while(T--)
    {
        solve();
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11884kb

input:

2
5
1 10 100 1000 10000
1 2 1 1 1
1 2
1 3
2 4
2 5
5
1 10 100 1000 10000
1 3 1 1 1
1 2
1 3
2 4
2 5

output:

10101
10111

result:

ok 2 number(s): "10101 10111"

Test #2:

score: 0
Accepted
time: 0ms
memory: 11880kb

input:

10
6
8 1 1 5 8 9
2 1 2 2 2 2
1 2
2 3
2 4
1 5
2 6
6
6 4 4 1 3 6
2 1 3 3 3 3
1 2
1 3
3 4
4 5
5 6
6
10 5 1 8 5 1
1 3 1 2 2 2
1 2
2 3
2 4
2 5
3 6
10
6 8 8 9 6 9 5 6 6 4
2 1 3 3 2 2 2 2 3 1
1 2
1 3
3 4
4 5
5 6
4 7
2 8
7 9
9 10
7
10 9 1 5 7 5 4
1 1 1 2 1 3 2
1 2
1 3
3 4
3 5
5 6
1 7
5
7 1 1 4 2
3 1 3 2 2
1...

output:

25
24
24
56
31
14
16
28
19
19

result:

ok 10 numbers

Test #3:

score: -100
Wrong Answer
time: 29ms
memory: 11880kb

input:

100000
10
9 1 7 9 5 1 10 5 3 8
2 1 1 3 1 2 2 3 3 1
1 2
2 3
3 4
1 5
2 6
2 7
6 8
7 9
7 10
3
6 6 1
2 1 2
1 2
1 3
10
6 5 3 7 1 5 1 9 7 3
3 1 3 3 1 3 2 2 2 3
1 2
1 3
3 4
4 5
2 6
6 7
4 8
7 9
1 10
7
2 8 9 7 7 9 10
2 3 2 2 3 2 1
1 2
2 3
1 4
3 5
4 6
3 7
1
8
1
1
4
2
7
9 9 9 8 4 2 7
3 1 2 1 1 1 1
1 2
2 3
2 4
3...

output:

49
12
41
45
8
4
38
22
20
21
5
19
23
44
26
5
21
28
28
32
36
15
5
26
38
36
20
35
27
36
20
9
32
32
22
11
41
15
20
54
38
20
45
36
20
29
24
4
37
44
30
45
17
17
36
29
3
6
24
44
25
28
50
13
5
1
44
27
17
21
15
17
17
24
29
39
10
39
38
26
22
24
9
17
41
7
28
33
51
18
14
14
7
35
23
13
11
43
30
24
35
2
43
33
17
...

result:

wrong answer 8845th numbers differ - expected: '38', found: '37'