コード
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')
}
}
}
Top comments (0)