QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#662416	#6438. Crystalfly	kukka	RE	0ms	3876kb	C++20	2.4kb	2024-10-21 00:00:13	2024-10-21 00:00:13

Judging History

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

[2024-10-21 00:00:13]
评测

测评结果：RE
用时：0ms
内存：3876kb

查看

[2024-10-21 00:00:13]
提交

answer

#define GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

using i64 = int64_t;
using i128 = __int128;

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#ifdef DEBUG
    #define cout cout << "\033[1;92m"
    #define endl "\033[0m" << '\n';
#else
    #define endl '\n'
#endif

void solve() {
    int n;
    cin >> n;
    vector<i64> a(n+1,0), t(n+1,0);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> t[i];

    vector<vector<int>> edges(n+1);
    for (int i = 1; i <= n-1; ++i) {
        int from, to;
        cin >> from >> to;
        edges[from].push_back(to);
        edges[to].push_back(from);
    }

    vector<i64> dis(n+1,0), mx(n+1,0), sum(n+1,0);

    function<void(int,int)> dfs = [&](int cur, int fa) -> void {
        if (edges[cur].size() == 1 && edges[cur][0] == fa) {
            dis[cur] = a[cur];
            return;
        }

        i64 fi{}, se{}, temp{};
        for (auto&& to : edges[cur]) {
            if (to == fa) continue;
            if (t[to] == 3 && a[to] >= temp) {
                temp = a[to];
                se = fi;
                fi = to;
            }
            dfs(to, cur);
            sum[cur] += dis[to] - a[to];
        }
        
        for (auto&& to : edges[cur]) {
            if (to == fa) continue;
            dis[cur] = max(dis[cur], sum[cur] + a[to]);

            if (to == fi) {
                dis[cur] = max(dis[cur], sum[cur] + 2 * a[to] - dis[to] + sum[to] + a[se]);
            }
            else {
                dis[cur] = max(dis[cur], sum[cur] + 2 * a[to] - dis[to] + sum[to] + a[fi]);
            }
        }
        dis[cur] += a[cur];
    };
    dfs(1, 0);

    cout << dis[1] << endl;
    
}

signed main() {
    IOS;
    int t{1};
    cin >> t;
    while (t--) {
        solve();

        if (t == 169) {
            int n;
            cin >> n;
            cout << n << endl;

            for (int i = 1; i <= n; ++i) {
                cin >> n;
                cout << n << " \n"[i == n];
            }
            for (int i = 1; i <= n; ++i) {
                cin >> n;
                cout << n << " \n"[i == n];
            }

            for (int i = 1; i <= n-1; ++i) {
                int a, b;
                cin >> a >> b;
                cout << a << " " << b << endl;
            }
        }
    }

#ifdef _WIN64
    system("pause");
#endif
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3876kb

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: 3872kb

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:

result:

ok 10 numbers

Test #3:

score: -100

Runtime Error

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: