#![allow(non_snake_case)] #![allow(dead_code)] #![allow(unused_macros)] #![allow(unused_imports)] use std::str::FromStr; use std::io::*; use std::collections::*; use std::cmp::*; struct Scanner> { iter: std::iter::Peekable, } macro_rules! exit { () => {{ exit!(0) }}; ($code:expr) => {{ if cfg!(local) { writeln!(std::io::stderr(), "===== Terminated =====") .expect("failed printing to stderr"); } std::process::exit($code); }} } impl> Scanner { pub fn new(iter: I) -> Scanner { Scanner { iter: iter.peekable(), } } pub fn safe_get_token(&mut self) -> Option { let token = self.iter .by_ref() .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::(); if token.is_empty() { None } else { Some(token) } } pub fn token(&mut self) -> String { self.safe_get_token().unwrap_or_else(|| exit!()) } pub fn get(&mut self) -> T { self.token().parse::().unwrap_or_else(|_| exit!()) } pub fn vec(&mut self, len: usize) -> Vec { (0..len).map(|_| self.get()).collect() } pub fn mat(&mut self, row: usize, col: usize) -> Vec> { (0..row).map(|_| self.vec(col)).collect() } pub fn char(&mut self) -> char { self.iter.next().unwrap_or_else(|| exit!()) } pub fn chars(&mut self) -> Vec { self.get::().chars().collect() } pub fn mat_chars(&mut self, row: usize) -> Vec> { (0..row).map(|_| self.chars()).collect() } pub fn line(&mut self) -> String { if self.peek().is_some() { self.iter .by_ref() .take_while(|&c| !(c == '\n' || c == '\r')) .collect::() } else { exit!(); } } pub fn peek(&mut self) -> Option<&char> { self.iter.peek() } } use std::mem::swap; struct UnionFind { parents: Vec, val: Vec, } impl UnionFind { fn new(n: usize) -> Self { UnionFind { parents: vec![-1; n], val: vec![0; n], } } fn unite(&mut self, x: usize, y: usize) { let mut px = self.root(x); let mut py = self.root(y); if px == py { return; } if -self.parents[px] < -self.parents[py] { swap(&mut px, &mut py); } self.parents[px] += self.parents[py]; self.parents[py] = px as i64; self.val[py] -= self.val[px]; } fn root(&mut self, x: usize) -> usize { let px = self.parents[x]; if px < 0 { return x; } self.root(px as usize) } fn add(&mut self, x: usize, v: i64) { let rx = self.root(x); self.val[rx] += v; } fn query(&self, x: usize) -> i64 { let mut ret = 0; let mut cur = x as i64; while self.parents[cur as usize] >= 0 { ret += self.val[cur as usize]; cur = self.parents[cur as usize]; } ret += self.val[cur as usize]; ret } } fn main() { let cin = stdin(); let cin = cin.lock(); let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char)); let N: usize = sc.get(); let Q: usize = sc.get(); let mut uf = UnionFind::new(N); for _ in 0..Q { let T: usize = sc.get(); match T { 1 => { let A: usize = sc.get::()-1; let B: usize = sc.get::()-1; uf.unite(A, B); }, 2 => { let A: usize = sc.get::()-1; let B: i64 = sc.get(); uf.add(A, B); }, 3 => { let A: usize = sc.get::()-1; let _: usize = sc.get(); println!("{}", uf.query(A)) } _ => panic!("error"), } } }