paizaラーニングレベルアップ問題集の「村人の友好関係」をやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集の[村人の友好関係](https://paiza.jp/works/mondai/s_rank_skillcheck_archive/group_popularity)をやってみました。
- - -
###### ランクBなら…
この問題の制約条件が$N\le100$, $Q\le100$ならば
- 友好度の行列を作る
- $q=1,2,...,Q$について
    - クエリ処理
    - $i=1,2,...,N-1$について
        - $j=i+1,i+2,...,N$について
            - 「村人$i$が同好会に属している」$\neq$「村人$j$が同好会に属している」ならば
                - 人気度を更新

でいいでしょう。以下、C++のサンプルプログラムを示します。
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
	int N, M, Q;
	cin >> N >> M >> Q;

    // 友好度行列
	vector<vector<int>> friendly(N, vector<int>(N, 0));
	for (int i = 0; i < M; i++) {
		int a, b, f;
		cin >> a >> b >> f;
		a--;
		b--;
		friendly[a][b] = f;
		friendly[b][a] = f;
	}

    // 同好会に属しているかどうか
	vector<bool> is_member(N, false);
	for (int k = 0; k < Q; k++) {
        // クエリ処理
		char op;
		int q;
		cin >> op >> q;
		q--;
		if (op == '+')
			is_member[q] = true;
		else if (op == '-')
			is_member[q] = false;

        // 人気度を算出
		int popularity = 0;
		for (int i = 0; i < N - 1; i++) {
			for (int j = i + 1; j < N; j++) {
				if (is_member[i] != is_member[j]) {
					if (friendly[i][j] > popularity)
						popularity = friendly[i][j];
				}
			}
		}
		cout << popularity << endl;
	}
}
```
$N^2Q\le10^7$程度までならこれでいいですが、この問題はランクSです！$N^2Q\le1.25\times10^{10}$の本問ではタイムオーバーです。
この問題では$N\le 500$はともかく、最大$50,000$クエリ飛んできます。せめて$O(NQ)$の計算量で押さえたいものです。
- - -
###### 別の視点で
クエリの処理を、村人×村人（頂点×頂点）ではなく、友好度を重みとする辺に注目することにします。つまり、
- 友好度の降順に見ていき、両端の頂点にあたる村人のうち一方のみ同好会に属している場合、その値を人気度とし、ループ終了する

ようにします。この時
- 村人$1$と村人$2$の友好度が$3$ 
- 村人$2$と村人$3$の友好度が$1$
- 村人$3$と村人$1$の友好度が$2$
```mermaid
graph LR
1<--3-->2
2<--1-->3
3<--2-->1
```
という関係が与えられたとして、友好度の降順に見ていったとき、「村人$2$が同好会にいて村人$3$はいないから人気度は$1$です」となることがあるでしょうか。その前に、村人$1$が同好会にいれば、村人$1$と村人$3$の友好度$2$が人気度となり、村人$1$が同好会にいなければ、村人$1$と村人$2$の友好度$3$が人気度として採用されるので、村人$2$と村人$3$の友好度$1$が人気度として採用されることはありません。
もっと言えば、友好度の降順に辺をとってグラフを構築していった時、村人$i$と村人$j$をつないだら閉路ができたとしましょう。この時「村人$i$が同好会に属していて村人$j$は属していないから人気度は$F_{i,j}$」ということはありません。既に$i$と$j$を直接つないでいない辺によってグラフが構築されており、その辺の少なくとも一ヶ所に同好会に属している人といない人の境目があり、すでに$F_{i,j}$より大きい人気度が定まっています。したがって、村人$i$と村人$j$をつなぐ辺は不要、ということになります。
- - -
###### 最小全域木ならぬ最大全域木
上記の考察により、[最小全域木](https://paiza.jp/works/mondai/tsp_problems/tsp_problems__mst)ならぬ、[最大全域木](https://paiza.jp/works/mondai/union_find_kraskal/union_find_kraskal__make_spanning)もどきを構築します。（もどきというのは、入力例2では村人は5人ですが村人3は完全に空気です。が、誰かと友好度0でつながっていることにしましょう）今回は、[クラスカル法](https://paiza.jp/works/mondai/union_find_kraskal/union_find_kraskal__kruskal)を利用して最大全域木もどきを構築します。（[プリム法](https://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95)もありますが、本記事では省略します）
以下、C++のサンプルプログラムです。
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>
using namespace std;

// ユニオンファインド
class UnionFind {
	vector<int> par;
	int root(int v) {
		if (par[v] < 0) {
			return v;
		}
		par[v] = root(par[v]);
		return par[v];
	}
public:
	UnionFind(int n) {
		par.resize(n, -1);
	}
	bool unite(int v, int u) {
		int rv = root(v);
		int ru = root(u);
		if (rv == ru) {
			return false;
		}
		if (par[rv] > par[ru]) {
			par[rv] = ru;
		} else {
			if (par[rv] == par[ru]) {
				par[rv]--;
			}
			par[ru] = par[rv];
		}
		return true;
	}
};

int main() {
	int N, M, Q;
	cin >> N >> M >> Q;

    // 優先度付きキュー
	priority_queue<pair<int, pair<int, int>>> PQ;
	for (int i = 0; i < M; i++) {
		int a, b;
		int f;
		cin >> a >> b >> f;
		a--;
		b--;
        // 友好度を優先度として、優先度付きキューに格納
		PQ.push( { f, { a, b } });
	}

    // クラスカル法で最大全域木もどきを構築する
	UnionFind uf(N);
	vector<pair<pair<int, int>, int>> mst;
	while (!PQ.empty()) { // 友好度の大きいものから処理
		pair<int, pair<int, int>> e = PQ.top();
		PQ.pop();
		int f;
		pair<int, int> p;
		tie(f, p) = e;
		int a, b;
		tie(a, b) = p;
		if (uf.unite(a, b)) {
			mst.push_back( { { a, b }, f });
		}
	}

    // 同好会に属しているかどうか
	vector<bool> is_member(N, false);
	for (int i = 0; i < Q; i++) {
        // クエリ処理
		char op;
		int q;
		cin >> op >> q;
		q--;
		if (op == '+')
			is_member[q] = true;
		else if (op == '-')
			is_member[q] = false;

        // 人気度を算出
		int popularity = 0;
		for (pair<pair<int, int>, int> e : mst) { // 最大全域木もどきの辺。最大N-1ループ。
			pair<int, int> p;
			int f;
			tie(p, f) = e;
			int a, b;
			tie(a, b) = p;
			if (is_member[a] != is_member[b]) {
				popularity = f;
				break;
			}
		}
		cout << popularity << endl;
	}
	return 0;
}
```