結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-05 16:30:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 246 ms / 2,000 ms |
コード長 | 1,321 bytes |
コンパイル時間 | 1,618 ms |
コンパイル使用メモリ | 125,224 KB |
最終ジャッジ日時 | 2025-01-14 07:13:07 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include<iostream>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<iomanip>#include<math.h>#include<complex>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#include<bitset>#include<functional>#include<assert.h>#include<numeric>using namespace std;#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )#define rep(i,n) REP(i,0,n)using ll = long long;const int inf=1e9+7;const ll longinf=1LL<<60 ;const ll mod=1e9+7 ;#define PI 3.141592653589793vector<int> to[101010];ll dp[101010][2];ll c[101010], b[101010];void DFS(int a, int p){vector<pair<ll, int>> kurabe;dp[a][0] = c[a];for(auto k: to[a]){if(k==p) continue;DFS(k, a);kurabe.push_back({dp[k][1]+b[a]+b[k]-dp[k][0], k});if(dp[k][1]>dp[k][0]) dp[a][0]+=dp[k][1];else dp[a][0]+=dp[k][0];dp[a][1]+=dp[k][0];}sort(kurabe.begin(), kurabe.end(), greater<>());ll nyan = dp[a][1];rep(i, kurabe.size()){if(kurabe[i].first>0) dp[a][1]+=kurabe[i].first;}}int main(){int n; cin >> n;rep(i, n) cin >> c[i];rep(i, n) cin >> b[i];rep(i, n-1){int u, v; cin >> u >> v; u--; v--;to[u].push_back(v); to[v].push_back(u);}DFS(0, -1);cout << max(dp[0][0], dp[0][1]) << endl;//cout << dp[0][1] << endl;}