結果
問題 | No.1221 木 *= 3 |
ユーザー |
👑 ![]() |
提出日時 | 2020-09-28 21:34:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 877 bytes |
コンパイル時間 | 1,543 ms |
コンパイル使用メモリ | 169,628 KB |
実行使用メモリ | 22,732 KB |
最終ジャッジ日時 | 2024-07-02 16:20:36 |
合計ジャッジ時間 | 5,033 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include<bits/stdc++.h>using namespace std;using LL = long long;using ULL = unsigned long long;#define rep(i,n) for(int i=0; i<(n); i++)struct Edge { int u, v; LL score; };int N;LL A[200000][2];Edge J[200000];vector<int> E[100000];LL Score[100000][2];int P[100000];void dfs(int p) {Score[p][0] = A[p][0];Score[p][1] = 0;for (int j : E[p]) {int to = J[j].v;if (P[p] == to) continue;P[to] = p;dfs(to);Score[p][0] += max(Score[to][0], Score[to][1]);Score[p][1] += max(Score[to][0], Score[to][1] + J[j].score);}}int main() {cin >> N;rep(j, 2) rep(i, N) cin >> A[i][j];rep(i, N - 1) {int u, v; cin >> u >> v; u--; v--;J[i] = { u,v,A[u][1] + A[v][1] };J[i + N] = { v,u,A[u][1] + A[v][1] };E[u].push_back(i);E[v].push_back(i + N);}P[0] = -1;dfs(0);cout << max(Score[0][0], Score[0][1]) << endl;return 0;}