結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-04 22:03:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 180 ms / 2,000 ms |
コード長 | 1,963 bytes |
コンパイル時間 | 1,988 ms |
コンパイル使用メモリ | 200,404 KB |
最終ジャッジ日時 | 2025-01-14 05:44:44 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:51:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 51 | scanf("%d%d", &a, &b); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); ++i)#define drep(i,n) for(int i = (n)-1; i >= 0; --i)#define srep(i,s,t) for (int i = s; i < t; ++i)using namespace std;typedef long long int ll;typedef pair<int,int> P;#define yn {puts("Yes");}else{puts("No");}#define MAX_N 200005vector<int> pre_G[MAX_N];vector<int> G[MAX_N];int par_[MAX_N];int flag_netsukigi[MAX_N];void make_netsukigi(int r){rep(i,MAX_N){G[i].clear();par_[i] = 0;flag_netsukigi[i] = 0;}queue<int> que;que.push(r);flag_netsukigi[r] = 1;par_[r] = -1;while(que.size() > 0){int x = que.front();que.pop();flag_netsukigi[x] = 1;rep(i,pre_G[x].size()){if(flag_netsukigi[pre_G[x][i]] == 0){par_[pre_G[x][i]] = x;G[x].push_back(pre_G[x][i]);que.push(pre_G[x][i]);}}}}ll dp[MAX_N][2];ll INF = 1001001001001001001;int main() {int n;cin >> n;ll a[n], b[n];rep(i,n) cin >> a[i];rep(i,n) cin >> b[i];rep(i,n-1){int a, b;scanf("%d%d", &a, &b);a--; b--; // 0-indexにするため.pre_G[a].push_back(b);pre_G[b].push_back(a);}make_netsukigi(0);rep(i,n)rep(j,2)dp[i][j] = -INF;queue<int> que;int son[n] = {};rep(i,n){son[i] = G[i].size();if(son[i] == 0){que.push(i);}}while(que.size()){int x = que.front();que.pop();dp[x][0] = a[x];dp[x][1] = 0;rep(i,G[x].size()){int y = G[x][i];dp[x][0] += max(dp[y][0], dp[y][1]);dp[x][1] += max(dp[y][0], dp[y][1] + b[x] + b[y]);}if(x == 0)break;son[par_[x]]--;if(son[par_[x]] == 0) que.push(par_[x]);}cout << max(dp[0][0], dp[0][1]) << endl;return 0;}