重み付きUnion-Find木(Weighted Union-Find Tree)

const Node = function (val) {
  this.val = val
  this.parent = this
  this.rank = 1
  this.weight = 0 // 親に対してのweight
}

const WeightedDisjointSet = function () {
  this.m = []
}

WeightedDisjointSet.prototype.add = function (val) {
  this.m[val] = new Node(val)
}

WeightedDisjointSet.prototype.merge = function (val1, val2, weight) {
  const p1 = this.find(val1)
  const p2 = this.find(val2)
  const w1 = this.weight(val1)
  const w2 = this.weight(val2)
  if (p1 === p2) {
    return
  }
  if (p2.rank <= p1.rank) {
    if (p1.rank == p2.rank) {
      p1.rank++
    }
    p2.parent = p1
    p2.weight = weight + w1 - w2
  } else {
    p1.parent = p2
    p1.weight = -weight - w1 + w2
  }
}

WeightedDisjointSet.prototype.find = function (val) {
  let cur = this.m[val]
  if (cur.parent != cur) {
    const root = this.find(cur.parent.val)
    cur.weight += cur.parent.weight
    cur.parent = root
  }
  return cur.parent
}

WeightedDisjointSet.prototype.diff = function (val1, val2) {
  const p1 = this.find(val1)
  const p2 = this.find(val2)
  if (p1 != p2) {
    return null
  }
  return this.weight(val2) - this.weight(val1)
}

WeightedDisjointSet.prototype.weight = function (val) {
  let weight = 0
  let cur = this.m[val]
  while (cur.parent != cur) {
    weight += cur.weight
    cur = cur.parent
  }
  return weight
}

let input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.trim().split("\n")
let n, q, d

for (let i = 0; i < lines.length; i++) {
  if (i === 0) {
    [n, q] = lines[i].split(" ")
    d = new WeightedDisjointSet()
    for (let i = 0; i < n; i++) {
      d.add(i)
    }
  } else {
    const [com, x, y, w] = lines[i].split(" ").map(v => parseInt(v))
    switch (com) {
      case 0:
        d.merge(x, y, w)
        break;
      case 1:
        const diff = d.diff(x, y)
        console.log(diff == null ? '?' : diff)
        break;
      default:
        throw Error('invalid com')
    }
  }
}