ARC106 B - Values

Problem:

B - Values (atcoder.jp)

Idea:

Check sum of nodes in the same connected components

Source:

int n, m;
Int a[N], b[N];

struct UF {
	vector<int> Parent;
	vector<int> Size;
	void init(int n) {
		Parent.resize(n);
		Size.resize(n);
		REP(i, n) {
			make_set(i);
		}
	}
	void make_set(int v) {
		Parent[v] = v;
		Size[v] = 1;
	}
	int find_set(int v) {
		if (v == Parent[v])
			return v;
		return Parent[v] = find_set(Parent[v]);
	}
	void union_sets(int a, int b) {
		a = find_set(a);
		b = find_set(b);
		if (a != b) {
			if (Size[a] < Size[b])
				swap(a, b);
			Parent[b] = a;
			Size[a] += Size[b];
		}
	}
};

void solve()
{
	cin >> n >> m;
	REP(i, n) cin >> a[i];
	REP(i, n) cin >> b[i];

	UF uf;
	uf.init(n);
	REP(i, m) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		uf.union_sets(u, v);
	}
	map<int, Int> mp1, mp2;
	REP(i, n) {
		int par = uf.find_set(i);
		mp1[par] += a[i];
		mp2[par] += b[i];
	}

	for (auto x : mp1) {
		int par = x.first;
		if (mp1[par] != mp2[par]) {
			cout << "No" << endl;
			return;
		}
	}
	cout << "Yes" << endl;
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(9);
	solve();
	return 0;
}