AtCoder Beginner Contest 396 E

https://atcoder.jp/contests/abc396/tasks/abc396_e

ノードXとYを重みWで結ぶ無向グラフと考えます。
入力例1では、A₁=vとすると、グラフを辿って、A₂=v XOR 3、A₃=v XOR 4となります。なので、
(v XOR 0) + (v XOR 3) + (v XOR 4)
を最小化するvを求めればよいです。
XORなので各ビットで考えればよいです。0, 3, 4を2進数にすると、

000
011
100

一番右のビットは010なので、vの一番下のビットを0とするとXORを取ると010、1とすると101になって、0を取る方が和が小さいことが分かります。要するに各ビットで考えて、0が多ければ0、1が多ければ1とすればよいです。

// Minimum XOR Path
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// UnionFind ////////////////////

use std::cmp::max;

type Node = usize;

struct UnionFind {
    parents: Vec<Node>,
    heights: Vec<i32>,
}

impl UnionFind {
    fn new(N: usize) -> UnionFind {
        let parents: Vec<Node> = (0..N).collect();
        let heights: Vec<i32> = vec![1; N];
        UnionFind { parents, heights }
    }
    
    fn is_root(&self, v: Node) -> bool {
        self.parents[v] == v
    }
    
    fn join(&mut self, u: Node, v: Node) {
        let r1 = self.root(u);
        let r2 = self.root(v);
        if r1 == r2 {
            return  // ここには来ないはず
        }
        
        let h1 = self.heights[r1];
        let h2 = self.heights[r2];
        if h1 <= h2 {   // r2にr1がぶら下がる
            self.parents[r1] = r2;
            self.heights[r2] = max(self.heights[r2], self.heights[r1]+1);
        }
        else {
            self.parents[r2] = r1;
            self.heights[r1] = max(self.heights[r1], self.heights[r2]+1);
        }
    }
    
    fn root(&self, v0: Node) -> Node {
        if self.is_root(v0) {
            v0
        }
        else {
            let p = self.parents[v0];
            self.root(p)
        }
    }
}


//////////////////// Graph ////////////////////

use std::collections::HashMap;

type Weight = i64;
type Edge = (Node, Node, Weight);

fn read_edge() -> Edge {
    let v: Vec<usize> = read_vec();
    (v[0]-1, v[1]-1, v[2] as Weight)
}

struct Graph {
    g: HashMap<Node, Vec<(Node, Weight)>>
}

impl Graph {
    fn len(&self) -> usize {
        self.g.len()
    }
    
    fn neighbors(&self, v: Node) -> Vec<(Node, Weight)> {
        if let Some(ref neighs) = self.g.get(&v) {
            neighs.to_vec()
        }
        else {
            vec![]
        }
    }
    
    fn divide_into_connected(&self) -> Vec<Graph> {
        let mut uf = UnionFind::new(self.len());
        for (&u, &ref vs) in self.g.iter() {
            for &(v, _w) in vs.iter() {
                uf.join(u, v)
            }
        }
        
        let mut m: HashMap<Node, Vec<Node>> = HashMap::new();
        for (&v, _) in self.g.iter() {
            let r = uf.root(v);
            let e = m.entry(r).or_insert(vec![]);
            (*e).push(v)
        }
        
        let mut gs: Vec<Graph> = vec![];
        for (_, vs) in m.into_iter() {
            let g = vs.into_iter().
                        map(|v| (v, self.g.get(&v).unwrap().to_vec())).
                                            collect::<HashMap<_, _>>();
            gs.push(Graph { g })
        }
        gs
    }
    
    fn create(N: usize, edges: Vec<Edge>) -> Graph {
        let mut g: HashMap<Node, Vec<(Node, Weight)>> =
                                (0..N).map(|v| (v, vec![])).collect();
        for (u, v, w) in edges.into_iter() {
            let e1 = g.entry(u).or_insert(vec![]);
            (*e1).push((v, w));
            let e2 = g.entry(v).or_insert(vec![]);
            (*e2).push((u, w))
        }
        Graph { g }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Edge>) {
    let v: Vec<usize> = read_vec();
    let (N, M) = (v[0], v[1]);
    let edges: Vec<Edge> = (0..M).map(|_| read_edge()).collect();
    (N, edges)
}

fn remove_duplicated_edges(edges: Vec<Edge>) -> Vec<Edge> {
    let mut dic: HashMap<(Node, Node), Weight> = HashMap::new();
    for (u, v, w) in edges {
        let uv = if u < v { (u, v) } else { (v, u) };
        if let Some(&w1) = dic.get(&uv) {
            if w1 != w {
                return vec![]
            }
        }
        else {
            dic.insert(uv, w);
        }
    }
    dic.into_iter().map(|((u, v), w)| (u, v, w)).collect::<Vec<Edge>>()
}

fn walk(v0: Node, graph: &Graph, A: &mut Vec<Weight>) -> bool {
    let neighs = graph.neighbors(v0);
    for (v, w) in neighs {
        if A[v] == -1 {
            A[v] = A[v0] ^ w;
            if !walk(v, &graph, A) {
                return false
            }
        }
        else if A[v] != A[v0] ^ w {
            return false
        }
    }
    true
}

fn num_bits(a: &Vec<Weight>) -> u64 {
    let max_a: Weight = *a.iter().max().unwrap();
    let mut n: u64 = 0;
    while (1 << n) <= max_a {
        n += 1
    }
    n
}

fn minimize(graph: Graph, A: &mut Vec<Weight>) {
    let a: Vec<Weight> = graph.g.keys().map(|&v| A[v]).collect();
    
    let mut s: i64 = 0;
    let L = graph.g.len() as i64;
    for i in 0..num_bits(&a) {
        let num_ones = a.iter().map(|&e| (e >> i) & 1).sum::<i64>();
        if num_ones * 2 > L {
            s |= 1 << i
        }
    }
    
    for &v in graph.g.keys() {
        A[v] ^= s
    }
}

fn F_each(graph: Graph, A: &mut Vec<Weight>) -> bool {
    let v0 = *graph.g.keys().next().unwrap();
    A[v0] = 0;
    let b = walk(v0, &graph, A);
    if b {
        minimize(graph, A)
    }
    b
}

fn F(N: usize, edges: Vec<Edge>) -> Vec<Weight> {
    if edges.is_empty() {
        return vec![0; N]
    }
    
    let filtered_edges = remove_duplicated_edges(edges);
    if filtered_edges.is_empty() {
        return vec![]
    }
    let graph = Graph::create(N, filtered_edges);
    let subgraphs = graph.divide_into_connected();
    let mut A: Vec<Weight> = vec![-1; N];
    for subg in subgraphs {
        if !F_each(subg, &mut A) {
            return vec![]
        }
    }
    A
}

fn main() {
    let (N, edges) = read_input();
    let A = F(N, edges);
    if A.is_empty() {
        println!("-1")
    }
    else {
        let s = A.into_iter().map(|a| a.to_string()).
                                collect::<Vec<String>>().join(" ");
        println!("{}", s)
    }
}