QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#658408#6438. Crystalflywzl19371WA 1ms5872kbC++202.1kb2024-10-19 16:46:452024-10-19 16:46:45

Judging History

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

  • [2024-10-19 16:46:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5872kb
  • [2024-10-19 16:46:45]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
typedef long long ll;
constexpr int maxn = 2e5+10;
constexpr ll mod = 998244353;
int head[maxn], ct;
struct Edge {
    int to, nxt;
} g[maxn << 1];
void add(int x, int y) {
    g[++ct] = {y, head[x]};
    head[x] = ct;
}
void solve() {
    ct = 0;
    memset(head, 0, sizeof(head));
    int n; cin >> n;
    int a[n+5]; rep(i,1,n) cin >> a[i];
    int t[n+5]; rep(i,1,n) cin >> t[i];
    for(int i=1;i<=n-1;i++) {
        int x, y; cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    bool vis[n+5] = {};
    ll f[n+5] = {};
    ll s[n+5] = {};
    f[0] = a[1];
    function<ll(int,int)> dfs = [&](int x, int fa) -> ll {
        if(vis[x]) return f[x];
        vis[x] = true;
        for(int i=head[x];i;i=g[i].nxt) {
            if(g[i].to == fa) continue;
            s[x] += dfs(g[i].to, x);
        }
        for(int i=head[x];i;i=g[i].nxt) {
            if(g[i].to == fa) continue;
            f[x] = max(f[x], a[g[i].to] + s[x]);
        }

        ll mx=0, mx2=0, mxi=-1, mxi2=-1;
        for(int i=head[x];i;i=g[i].nxt) {
            if(g[i].to == fa) continue;
            if(f[g[i].to] >= mx) {
                mx2 = mx;
                mxi2 = mxi;
                mx = f[g[i].to];
                mxi = g[i].to;
            } else if(f[g[i].to] > mx2) {
                mx2 = f[g[i].to];
                mxi2 = g[i].to;
            }
        }
        for(int i=head[x];i;i=g[i].nxt) {
            if(g[i].to == fa) continue;
            if(t[g[i].to] != 3) continue;
            if(g[i].to != mxi) {
                f[x] = max(f[x], s[x] - f[mxi] + a[mxi] + s[mxi] + a[g[i].to]);
            } else {
                f[x] = max(f[x], s[x] - f[mxi2] + a[mxi2] + s[mxi2] + a[g[i].to]);
            }
        }
        return f[x];
    };
    dfs(1, 0);
    ll out = 0;
    for(int i=1;i<=n;i++)
        out = max(out, f[i]);
    cout << out + a[1] << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin>>t;
    while(t--) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5872kb

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: -100
Wrong Answer
time: 1ms
memory: 4340kb

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
89348
22356
44720
94489867837599
14
22348
21
19
22342

result:

wrong answer 2nd numbers differ - expected: '24', found: '89348'