macro_rules! chmin { ($a: expr, $b: expr) => { $a = std::cmp::min($a, $b); }; } macro_rules! chmax { ($a: expr, $b: expr) => { $a = std::cmp::max($a, $b); }; } const INF: usize = std::usize::MAX; fn dfs( i: usize, p: usize, g: &Vec>, par: &mut Vec, max: &mut Vec, min: &mut Vec, order: &mut Vec, ) { par[i] = p; max[i] = 0; min[i] = INF; for &j in &g[i] { if j == p { continue; } dfs(j, i, g, par, max, min, order); chmax!(max[i], max[j] + 1); chmin!(min[i], min[j] + 1); } if min[i] == INF { min[i] = 0; } order.push(i); } fn main() { let stdin = std::io::stdin(); let mut rd = ProconReader::new(stdin.lock()); let n: usize = rd.get(); let mut g = vec![vec![]; n]; for _ in 0..(n - 1) { let a: usize = rd.get(); let b: usize = rd.get(); g[a - 1].push(b - 1); g[b - 1].push(a - 1); } let mut par = vec![0; n]; let mut sub_max = vec![0; n]; let mut sub_min = vec![INF; n]; let mut order = Vec::new(); dfs( 0, std::usize::MAX, &g, &mut par, &mut sub_max, &mut sub_min, &mut order, ); order.reverse(); let mut par_max = vec![0; n]; let mut par_min = vec![INF; n]; par_max[0] = 0; par_min[0] = 0; let mut max = vec![0; n]; let mut min = vec![INF; n]; max[0] = sub_max[0]; min[0] = sub_min[0]; assert_eq!(order[0], 0); for &i in &order[1..] { chmax!(par_max[i], par_max[par[i]] + 1); chmin!(par_min[i], par_min[par[i]] + 1); chmax!(max[i], par_max[i] + sub_max[i]); chmin!(min[i], par_min[i] + sub_min[i]); } let ok = max.iter().zip(min.iter()).all(|(min, max)| min == max); if ok { println!("Yes"); } else { println!("No"); } } pub struct ProconReader { r: R, l: String, i: usize, } impl ProconReader { pub fn new(reader: R) -> Self { Self { r: reader, l: String::new(), i: 0, } } pub fn get(&mut self) -> T where T: std::str::FromStr, ::Err: std::fmt::Debug, { self.skip_blanks(); assert!(self.i < self.l.len()); // remain some character assert_ne!(&self.l[self.i..=self.i], " "); let rest = &self.l[self.i..]; let len = rest.find(' ').unwrap_or_else(|| rest.len()); // parse self.l[self.i..(self.i + len)] let val = rest[..len] .parse() .unwrap_or_else(|e| panic!("{:?}, attempt to read `{}`", e, rest)); self.i += len; val } fn skip_blanks(&mut self) { loop { match self.l[self.i..].find(|ch| ch != ' ') { Some(j) => { self.i += j; break; } None => { let mut buf = String::new(); let num_bytes = self .r .read_line(&mut buf) .unwrap_or_else(|_| panic!("invalid UTF-8")); assert!(num_bytes > 0, "reached EOF :("); self.l = buf .trim_end_matches('\n') .trim_end_matches('\r') .to_string(); self.i = 0; } } } } pub fn get_vec(&mut self, n: usize) -> Vec where T: std::str::FromStr, ::Err: std::fmt::Debug, { (0..n).map(|_| self.get()).collect() } pub fn get_chars(&mut self) -> Vec { self.get::().chars().collect() } }