#1161406 (Rust) No.3514 Majority Driven Tree

• 問題: No.3514 Majority Driven Tree
• ユーザー: akakimidori
• 提出日時: 2026-04-24 22:12:20
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: WA
• 実行時間: -
• コード長: 9,160 bytes
• コンパイル時間: 8,974 ms
• コンパイル使用メモリ: 197,756 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-24 22:12:38
• 合計ジャッジ時間: 12,352 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 2 WA * 35

ソースコード

// 一つ選んで塗る操作をし切ってから過半数で塗る
//
// DPしようと思うと
// 親が何であろうが黒にできる
// 白のまま、親が黒である必要がある

fn main() {
    input! {
        n: usize,
        e: [(usize1, usize1); n - 1],
    }
    for r in 0..1 {
        let mut hld = HLD::new(n);
        for &(a, b) in e.iter() {
            hld.add_edge(a, b);
        }
        hld.build(r);
        let mut dp = vec![(0i32, 0i32); n];
        for i in (0..n).rev() {
            let v = hld.vertex(i);
            let mut c = hld.child[v].iter().map(|u| dp[*u]).collect::<Vec<_>>();
            c.sort_by_key(|p| p.0);
            let neighbor = if v == r { c.len() } else { c.len() + 1 };

            // 黒で塗る場合
            let mut can = 1;
            for &(a, b) in c.iter() {
                can += a.min(b);
            }

            // 子から黒を伝播させられる時
            if neighbor / 2 + 1 <= c.len() {
                let need = neighbor / 2 + 1;
                can = can.min(c.iter().take(need).map(|p| p.0).sum::<i32>());
            }

            // 親が黒であるなら可能な時
            dp[v] = (can, c.iter().take(neighbor / 2).map(|p| p.0).sum::<i32>());
        }
        println!("{}", dp[r].0);
    }
}

// ---------- 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 ----------
// ---------- begin Heavy-Light decomposition ----------
pub struct HLD {
    size: usize,
    edge: Vec<(usize, usize)>,
    child: Vec<Vec<usize>>,
    path_root: Vec<usize>,
    parent: Vec<usize>,
    left: Vec<usize>,
    right: Vec<usize>,
    inverse: Vec<usize>,
}

impl HLD {
    pub fn new(size: usize) -> Self {
        assert!(size <= 10usize.pow(8));
        HLD {
            size: size,
            edge: Vec::with_capacity(size - 1),
            child: Vec::new(),
            path_root: Vec::new(),
            parent: Vec::new(),
            left: Vec::new(),
            right: Vec::new(),
            inverse: Vec::new(),
        }
    }
    pub fn add_edge(&mut self, a: usize, b: usize) {
        assert!(a != b && a < self.size && b < self.size);
        self.edge.push((a, b));
    }
    pub fn build(&mut self, root: usize) {
        assert!(self.edge.len() + 1 == self.size);
        let size = self.size;
        let mut cnt = vec![0; size];
        for &(a, b) in self.edge.iter() {
            cnt[a] += 1;
            cnt[b] += 1;
        }
        let mut child = cnt
            .into_iter()
            .map(|c| Vec::with_capacity(c))
            .collect::<Vec<_>>();
        for &(a, b) in self.edge.iter() {
            child[a].push(b);
            child[b].push(a);
        }
        let mut parent = vec![size; size];
        let mut q = Vec::with_capacity(size);
        q.push(root);
        parent[root] = root;
        for i in 0..size {
            let v = q[i];
            for u in child[v].clone() {
                assert!(parent[u] == size);
                parent[u] = v;
                child[u].retain(|e| *e != v);
                q.push(u);
            }
        }
        let mut sum = vec![1; size];
        for &v in q.iter().rev() {
            let child = &mut child[v];
            if !child.is_empty() {
                let (pos, _) = child.iter().enumerate().max_by_key(|p| sum[*p.1]).unwrap();
                child.swap(0, pos);
                sum[v] = 1 + child.iter().fold(0, |s, a| s + sum[*a]);
            }
        }
        let mut path_root = (0..size).collect::<Vec<_>>();
        let mut left = vec![0; size];
        let mut right = vec![0; size];
        let mut dfs = vec![(root, false)];
        let mut id = 0;
        while let Some((v, end)) = dfs.pop() {
            if end {
                right[v] = id;
                continue;
            }
            left[v] = id;
            id += 1;
            dfs.push((v, true));
            let child = &child[v];
            if !child.is_empty() {
                for &u in child[1..].iter() {
                    path_root[u] = u;
                    dfs.push((u, false));
                }
                let u = child[0];
                path_root[u] = path_root[v];
                dfs.push((u, false));
            }
        }
        let mut inverse = vec![size; size];
        for (i, l) in left.iter().enumerate() {
            inverse[*l] = i;
        }
        self.child = child;
        self.parent = parent;
        self.left = left;
        self.right = right;
        self.path_root = path_root;
        self.inverse = inverse;
    }
    pub fn lca(&self, mut a: usize, mut b: usize) -> usize {
        assert!(a < self.size && b < self.size);
        let path = &self.path_root;
        let parent = &self.parent;
        let index = &self.left;
        while path[a] != path[b] {
            if index[a] > index[b] {
                std::mem::swap(&mut a, &mut b);
            }
            b = parent[path[b]];
        }
        std::cmp::min((index[a], a), (index[b], b)).1
    }
    pub fn path(
        &self,
        src: usize,
        dst: usize,
        up: &mut Vec<(usize, usize)>,
        down: &mut Vec<(usize, usize)>,
    ) {
        assert!(src < self.size && dst < self.size);
        up.clear();
        down.clear();
        let path = &self.path_root;
        let parent = &self.parent;
        let index = &self.left;
        let mut x = src;
        let mut y = dst;
        while path[x] != path[y] {
            if index[x] > index[y] {
                let p = path[x];
                assert!(p == path[p]);
                up.push((index[p], index[x] + 1));
                x = parent[p];
            } else {
                let p = path[y];
                assert!(p == path[p]);
                down.push((index[p], index[y] + 1));
                y = parent[p];
            }
        }
        if index[x] <= index[y] {
            down.push((index[x], index[y] + 1));
        } else {
            up.push((index[y], index[x] + 1));
        }
        down.reverse();
    }
    pub fn sub_tree(&self, v: usize) -> (usize, usize) {
        assert!(v < self.size);
        (self.left[v], self.right[v])
    }
    pub fn parent(&self, v: usize) -> Option<usize> {
        assert!(v < self.size);
        let p = self.parent[v];
        if p == v {
            None
        } else {
            Some(p)
        }
    }
    // s -> t へのパスの2番目の頂点を返す
    pub fn next(&self, s: usize, t: usize) -> usize {
        assert!(s < self.size && t < self.size && s != t);
        let (a, b) = self.sub_tree(s);
        let (c, d) = self.sub_tree(t);
        if !(a <= c && d <= b) {
            return self.parent[s];
        }
        let mut pos = t;
        let mut pre = t;
        while self.path_root[s] != self.path_root[pos] {
            pre = self.path_root[pos];
            pos = self.parent[pre];
        }
        if s == pos {
            pre
        } else {
            self.child[s][0]
        }
    }
    pub fn vertex(&self, x: usize) -> usize {
        assert!(x < self.size);
        self.inverse[x]
    }
    pub fn jump(
        &self,
        s: usize,
        t: usize,
        mut k: usize,
        up: &mut Vec<(usize, usize)>,
        down: &mut Vec<(usize, usize)>,
    ) -> Option<usize> {
        assert!(s.max(t) < self.size);
        self.path(s, t, up, down);
        for (l, r) in up.drain(..) {
            if k < r - l {
                return Some(self.vertex(r - 1 - k));
            }
            k -= r - l;
        }
        for (l, r) in down.drain(..) {
            if k < r - l {
                return Some(self.vertex(l + k));
            }
            k -= r - l;
        }
        None
    }
}
// ---------- end Heavy-Light decomposition ----------