This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B"
#include "template/template.hpp"
#include "structure/potentialized-union-find-tree.hpp"
ll op(ll a, ll b) {
return a + b;
}
ll invop(ll a, ll b) {
return a - b;
}
ll e() {
return 0LL;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
PotentializedUnionFindTree<ll,op,invop,e> puf(n);
for(int i=0; i<q; i++) {
int t; cin >> t;
int x, y; cin >> x >> y;
if (t == 0) {
ll z; cin >> z;
puf.merge(x,y,-z);
}
else if (t == 1) {
if (puf.same(x,y)) {
ll diff = puf.diff(y,x);
cout << diff << endl;
}
else cout << "?" << endl;
}
}
return 0;
}
#line 1 "test/verify/structure/aoj-dsl1-b.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B"
#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 1 "structure/potentialized-union-find-tree.hpp"
#include <vector>
template <typename T, T(*op)(T, T), T(*invop)(T, T), T(*e)()>
struct PotentializedUnionFindTree {
private:
int n;
std::vector<int> parent;
std::vector<int> rank;
std::vector<T> potential;
public:
explicit PotentializedUnionFindTree(int _n) : n(_n), parent(_n), rank(_n, 0), potential(_n, e()) {
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int merge(int a, int b, T d) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
int rootA = leader(a);
int rootB = leader(b);
if (rootA == rootB) return rootA;
T new_potential = invop(potential[a], op(d, potential[b]));
if (rank[rootA] < rank[rootB]) {
std::swap(rootA, rootB);
new_potential = invop(e(), new_potential);
}
parent[rootB] = rootA;
potential[rootB] = new_potential;
if (rank[rootA] == rank[rootB]) {
rank[rootA]++;
}
return rootA;
}
bool same(int a, int b) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < n);
if (parent[a] != a) {
int root = leader(parent[a]);
potential[a] = op(potential[a], potential[parent[a]]);
parent[a] = root;
}
return parent[a];
}
int size(int a) {
assert(0 <= a && a < n);
int root = leader(a);
int size = 0;
for (int i = 0; i < n; ++i) {
if (leader(i) == root) {
++size;
}
}
return size;
}
T diff(int a, int b) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(same(a,b));
return invop(potential[a], potential[b]);
}
};
#line 5 "test/verify/structure/aoj-dsl1-b.test.cpp"
ll op(ll a, ll b) {
return a + b;
}
ll invop(ll a, ll b) {
return a - b;
}
ll e() {
return 0LL;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
PotentializedUnionFindTree<ll,op,invop,e> puf(n);
for(int i=0; i<q; i++) {
int t; cin >> t;
int x, y; cin >> x >> y;
if (t == 0) {
ll z; cin >> z;
puf.merge(x,y,-z);
}
else if (t == 1) {
if (puf.same(x,y)) {
ll diff = puf.diff(y,x);
cout << diff << endl;
}
else cout << "?" << endl;
}
}
return 0;
}