QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797280#6438. CrystalflyFUCKUCUPWA 70ms5740kbC++201.2kb2024-12-02 20:07:462024-12-02 20:07:53

Judging History

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

  • [2024-12-02 20:07:53]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:5740kb
  • [2024-12-02 20:07:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int T, n, a[maxn], t[maxn];
long long f[maxn];
vector<int> g[maxn];
void dfs(int u, int pre) {
  f[u] = a[u];
  int mx = 0, cmx = 0;
  long long sum = 0;
  for(auto &v : g[u]) if(v != pre) {
    if(t[v] == 3) {
      if (a[v] > mx) cmx = mx, mx = a[v];
      else if (a[v] > cmx) cmx = a[v];
    }
    dfs(v, u), sum += f[v] - a[v];
  }
  for(auto &v : g[u]) if(v != pre) {
    f[u] = max(f[u], a[u] + a[v] + sum);
    if(t[v] == 3 && a[v] == mx) f[u] = max(f[u], sum - f[v] + a[u] + a[v] + cmx);
    else f[u] = max(f[u], sum - f[v] + a[u] + 2 * a[v] + mx);
  }
}
inline void solve() {
  cin >> n;
  for(int i = 1; i <= n; ++i) cin >> a[i];
  for(int i = 1; i <= n; ++i) cin >> t[i];
  for(int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
  }
  dfs(1, 0), cout << f[1] << '\n';
//  for(int i = 1; i <= n; ++i) cout << f[i] << ' '; cout << '\n';
  for(int i = 1; i <= n; ++i) g[i].clear();
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cin >> T;
  while(T--) solve();
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3736kb

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: 1ms
memory: 5740kb

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: 70ms
memory: 3624kb

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
40
45
8
4
38
22
20
21
5
19
23
44
26
5
21
28
26
26
36
15
5
26
38
36
20
35
27
36
20
9
32
29
22
11
41
15
20
50
38
20
45
36
20
29
24
4
30
44
30
44
17
17
36
29
3
6
24
44
25
28
49
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 3rd numbers differ - expected: '41', found: '40'