QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#658408 | #6438. Crystalfly | wzl19371 | WA | 1ms | 5872kb | C++20 | 2.1kb | 2024-10-19 16:46:45 | 2024-10-19 16:46:45 |
Judging History
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'