各社員が属するプロジェクトを bitset で管理します。 これらは木 DP の要領で \(O(NM / \mathrm{wordsize})\) 時間で計算できます。

求めたい値は \(i_a\) が属するプロジェクトと \(j_a\) が属するプロジェクトの積集合のサイズです。 すなわち、bitwise AND の popcount が求められればよいです。 これはクエリあたり \(O(M / \mathrm{wordsize})\) 時間で処理できます。

結局、全体で \(O(NM / \mathrm{wordsize})\) 時間で解けます。