#1193449 (Rust) No.3769 Even Contraction

• 問題: No.3769 Even Contraction
• ユーザー: akakimidori
• 提出日時: 2026-10-17 10:12:39
• 言語: Rust (1.99.0 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 49 ms / 2,000 ms
• コード長: 4,536 bytes
• コンパイル時間: 9,292 ms
• コンパイル使用メモリ: 172,984 KB
• 実行使用メモリ: 37,700 KB
• 最終ジャッジ日時: 2026-10-17 10:12:54
• 合計ジャッジ時間: 7,605 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

コンパイルメッセージ

warning: unused import: `std::io::Write`
 --> src/main.rs:2:5
  |
2 | use std::io::Write;
  |     ^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

warning: unused variable: `i`
  --> src/main.rs:38:14
   |
38 |         for (i, c) in c.iter().enumerate() {
   |              ^ help: if this is intentional, prefix it with an underscore: `_i`
   |
   = note: `#[warn(unused_variables)]` (part of `#[warn(unused)]`) on by default

warning: type alias `Map` is never used
 --> src/main.rs:4:6
  |
4 | type Map<K, V> = BTreeMap<K, V>;
  |      ^^^
  |
  = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: type alias `Set` is never used
 --> src/main.rs:5:6
  |
5 | type Set<T> = BTreeSet<T>;
  |      ^^^

warning: type alias `Deque` is never used
 --> src/main.rs:6:6
  |
6 | type Deque<T> = VecDeque<T>;
  |      ^^^^^

ソースコード

use std::collections::*;
use std::io::Write;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    input! {
        n: usize,
        e: [(usize1, usize1); n - 1],
        a: [usize; n],
    }
    let mut g = vec![vec![]; n];
    for (a, b) in e {
        g[a].push(b);
        g[b].push(a);
    }
    for r in 0..1 {
        let dp = dfs(r, n, &g, &a);
        println!("{}", dp[0].max(dp[1]));
    }
}

const INF: i32 = 10i32.pow(7);

// 元の値、1, 02なら将来1に化けた時の値
fn dfs(v: usize, p: usize, g: &[Vec<usize>], a: &[usize]) -> [i32; 3] {
    let mut c = vec![vec![]; 3];
    for &u in g[v].iter() {
        if u != p {
            c[a[u]].push(dfs(u, v, g, a));
        }
    }
    let mut res = [-INF, -INF, -INF];
    if a[v] == 1 {
        res[1] = 0;
        for (i, c) in c.iter().enumerate() {
            for a in c.iter() {
                res[1] += a[0].max(a[1] + 1);
            }
        }
    } else {
        let r = a[v];
        // 根変わらず
        res[0] = 0;
        res[0] += c[r].iter().map(|a| a[1].max(a[0] + 1)).sum::<i32>();
        res[0] += c[r ^ 2].iter().map(|a| a[1].max(a[0])).sum::<i32>();
        res[0] += c[1].iter().map(|a| a[1]).sum::<i32>();
        // 根変わらず、1予約
        res[2] = 0;
        res[2] += c[r].iter().map(|a| a[1].max(a[2]) + 1).sum::<i32>();
        res[2] += c[r ^ 2].iter().map(|a| (a[1] + 1).max(a[0])).sum::<i32>();
        res[2] += c[1].iter().map(|a| a[1] + 1).sum::<i32>();
        // 根を1にする
        if c[r ^ 2].len() > 0 {
            let x = c[r].iter().map(|p| p[1].max(p[2]) + 1).sum::<i32>();
            let y = c[r ^ 2].iter().map(|p| p[0].max(p[1] + 1)).sum::<i32>();
            let z = c[r ^ 2].iter().map(|p| p[2] - p[0].max(p[1] + 1)).max().unwrap() + 1;
            let s = c[1].iter().map(|p| p[1] + 1).sum::<i32>();
            res[1] = x + y + z + s;
        }
        // 将来1になるやつの手前に入る
        if c[r].len() > 0 {
            let x = c[r].iter().map(|p| p[1].max(p[2]) + 1).sum::<i32>();
            let y = c[r].iter().map(|p| p[1] + 1 - (p[1].max(p[2]) + 1)).max().unwrap();
            let s = c[r ^ 2].iter().map(|p| p[0].max(p[1] + 1)).chain(c[1].iter().map(|p| p[1] + 1)).sum::<i32>();
            res[1] = res[1].max(x + y + s);
        }
    }
    //println!("root: {v}: {:?}", res);
    res
}

/*

1頂点にできるかの判定ができるか？

00->0
11->1
22->2
02->1

0,2 は隣接してたら操作していい？
0-2-2-0 とか1を作るのが最適

1は貪欲にやっていい

0,2 と連結な1の個数が重要そう？

木dpしようと思うと
根の値が

0,1,2である時操作回数の最大値
0,2 については将来1に化ける時の追加の操作回数の最大値を足し込んだ値
も管理すればいい？

無駄に状態数多くしてるが根の値は1なら1しかない、0なら01 しかない

根を親方向にマージするという遷移が抜けている

根の元の色も覚えて遷移？

*/

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------