package main import ( "bufio" "fmt" "os" "strconv" ) func configure(scanner *bufio.Scanner) { scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, 1000005), 1000005) } func getNextString(scanner *bufio.Scanner) string { scanned := scanner.Scan() if !scanned { panic("scan failed") } return scanner.Text() } func getNextInt(scanner *bufio.Scanner) int { i, _ := strconv.Atoi(getNextString(scanner)) return i } func getNextInt64(scanner *bufio.Scanner) int64 { i, _ := strconv.ParseInt(getNextString(scanner), 10, 64) return i } func getNextFloat64(scanner *bufio.Scanner) float64 { i, _ := strconv.ParseFloat(getNextString(scanner), 64) return i } func main() { fp := os.Stdin wfp := os.Stdout extra := 0 if os.Getenv("I") == "IronMan" { fp, _ = os.Open(os.Getenv("END_GAME")) extra = 100 } scanner := bufio.NewScanner(fp) configure(scanner) writer := bufio.NewWriter(wfp) defer func() { r := recover() if r != nil { fmt.Fprintln(writer, r) } writer.Flush() }() solve(scanner, writer) for i := 0; i < extra; i++ { fmt.Fprintln(writer, "-----------------------------------") solve(scanner, writer) } } func solve(scanner *bufio.Scanner, writer *bufio.Writer) { n := getNextInt(scanner) q := getNextInt(scanner) d := NewDsu(n) g := make([][]int, n) add := make([]int, n) sum := make([]int, n) for i := 0; i < n; i++ { g[i] = append(g[i], i) } for q > 0 { q-- t := getNextInt(scanner) a := getNextInt(scanner) - 1 b := getNextInt(scanner) switch t { case 1: b-- if !d.Same(a, b) { if d.Size(a) < d.Size(b) { a, b = b, a } la := d.Leader(a) lb := d.Leader(b) // lb -> la for _, v := range g[lb] { sum[v] += add[lb] sum[v] -= add[la] g[la] = append(g[la], v) } g[lb] = nil add[lb] = 0 d.Merge(a, b) } case 2: add[d.Leader(a)] += b case 3: fmt.Fprintln(writer, sum[a]+add[d.Leader(a)]) } } } // Dsu Data structures and algorithms for disjoint set union problems type Dsu struct { n int parentOrSize []int } // NewDsu Constructor func NewDsu(n int) *Dsu { p := make([]int, n) for i := 0; i < n; i++ { p[i] = -1 } return &Dsu{parentOrSize: p, n: n} } // Merge adds an edge (a, b). func (d *Dsu) Merge(a, b int) int { x := d.Leader(a) y := d.Leader(b) if x == y { return x } if d.parentOrSize[x] > d.parentOrSize[y] { x, y = y, x } d.parentOrSize[x] += d.parentOrSize[y] d.parentOrSize[y] = x return x } // Same returns whether the vertices a and b are in the same connected component. func (d *Dsu) Same(a, b int) bool { return d.Leader(a) == d.Leader(b) } // Leader returns the representative of the connected component that contains the vertex a. func (d *Dsu) Leader(a int) int { if d.parentOrSize[a] < 0 { return a } d.parentOrSize[a] = d.Leader(d.parentOrSize[a]) return d.parentOrSize[a] } // Size returns the size of the connected component that contains the vertex a. func (d *Dsu) Size(a int) int { return -d.parentOrSize[d.Leader(a)] } // Groups divides the graph into connected components and returns the list of them. func (d *Dsu) Groups() [][]int { result := make([][]int, d.n) for i := 0; i < d.n; i++ { l := d.Leader(i) result[l] = append(result[l], i) } return result }