結果
問題 | No.1221 木 *= 3 |
ユーザー |
|
提出日時 | 2020-09-05 00:15:07 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 1,958 bytes |
コンパイル時間 | 11,982 ms |
コンパイル使用メモリ | 377,928 KB |
実行使用メモリ | 27,904 KB |
最終ジャッジ日時 | 2024-11-26 21:14:30 |
合計ジャッジ時間 | 14,566 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
use std::cmp::*;macro_rules !input {(source =$s :expr ,$($r :tt ) *) =>{let mut iter =$s .split_whitespace () ;let mut next =||{iter .next () .unwrap () };input_inner !{next ,$($r ) *} } ;($($r :tt ) *) =>{let stdin =std ::io ::stdin () ;let mut bytes =std ::io ::Read ::bytes (std ::io ::BufReader::new (stdin .lock () ) ) ;let mut next =move ||->String {bytes .by_ref () .map (|r |r .unwrap () as char ) .skip_while (|c |c .is_whitespace () ).take_while (|c |!c .is_whitespace () ) .collect () } ;input_inner !{next ,$($r ) *} } ;}macro_rules !input_inner {($next :expr ) =>{} ;($next :expr ,) =>{} ;($next :expr ,$var :ident :$t :tt $($r :tt ) *) =>{let $var =read_value !($next,$t ) ;input_inner !{$next $($r ) *} } ;}macro_rules !read_value {($next :expr ,($($t :tt ) ,*) ) =>{($(read_value !($next ,$t ) ) ,*) } ;($next :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ).map (|_ |read_value !($next ,$t ) ) .collect ::<Vec <_ >>() } ;($next :expr ,chars ) =>{read_value !($next ,String ) .chars () .collect ::<Vec<char >>() } ;($next :expr ,usize1 ) =>{read_value !($next ,usize ) -1 } ;($next :expr ,$t :ty ) =>{$next () .parse ::<$t >() .expect ("Parseerror" ) } ;}fn main() {input! {n: usize,a: [i64; n],b: [i64; n],uv: [(usize, usize); n-1]}let mut to = vec![vec![]; n];for &(u, v) in uv.iter() {to[u - 1].push(v - 1);to[v - 1].push(u - 1);}let mut dp = vec![vec![0; 2]; n];dfs(0, 0, &to, &a, &b, &mut dp);let ans = max(dp[0][0], dp[0][1]);println!("{}", ans);}fn dfs(u: usize,p: usize,to: &Vec<Vec<usize>>,a: &Vec<i64>,b: &Vec<i64>,dp: &mut Vec<Vec<i64>>,) {dp[u][0] = a[u];for &v in to[u].iter() {if v == p {continue;}dfs(v, u, to, a, b, dp);dp[u][0] += max(dp[v][0], dp[v][1]);dp[u][1] += max(dp[v][0], dp[v][1] + b[u] + b[v]);}}