日記の公開設定を $\left( i \right)$ にした人をタイプ $i$ と呼ぶことにします。また、人を頂点に友人関係を辺に見立てたグラフを考えます。各タイプの人数で場合分けをします。

タイプ \(1\) の人がいる場合

タイプ $1$ の人に対応する頂点は他の $N-1$ 個の全ての頂点と辺で直接繋がっている必要があります。よって、そのように辺を引いた場合の本数またはコストが明らかに必要です。また、このように辺を引くのが十分でもあります。

証明

タイプ $2$ の人について、タイプ $1$ の人を経由することで条件を満たすことができます。また、明らかにグラフは連結なのでタイプ $3$ の人についても条件が満たされています。よって、これ以上辺を引く必要がないのでこれで十分です。

これより、この場合は $O(N^2)$ で解くことができました。

以降タイプ $1$ の人は存在しないとします。タイプ $2,3$ の人の条件は共にグラフが連結であることを要求するので、最低でも $N-1$ 本の辺が必要です。また、頂点 $1$ から他の全ての頂点に辺を引いたグラフを考えるとこれでタイプ $2,3$ の人の条件が満たされているので、 $N-1$ 本の辺で十分です。

タイプ \(2\) の人がいる場合

タイプ $2$ の人が $2$ 人いるとします。それを人 $p,q$ とします。
頂点 $p,q$ が直接辺で繋がれているとします。この時、他の頂点について頂点 $p,q$ のいずれか $1$ つと繋がれていることが必要十分です。各頂点についてどちらと繋げるかは独立かつ貪欲に決められるので $O(N)$ でこの場合を考慮できます。
そうでない場合、ある頂点 $r$ について頂点 $p,r$ を結ぶ辺と頂点 $q,r$ を結ぶ辺があります。これら $3$ つ以外の頂点については頂点 $r$ と結ばれている必要があります。 $r$ の候補は $O(N)$ 通りなので、これは $O(N^2)$ で解くことができます。

タイプ $2$ の人が $3$ 人以上いるとします。この時、他の全ての頂点と辺で繋がれている頂点が存在します。

証明

$N=3$ の時、明らかに成り立ちます。 $N \geq 4$ とします。

他の全ての頂点と辺で繋がれている頂点がないならば条件が満たされないことを示します。これを示せば対偶より元の命題は示されます。
頂点の次数を考えます。グラフが木であることを考えると全頂点の次数の総和は $2N-2$ です。よって次数が $2$ 以上の頂点が明らかにあります。他の全ての頂点と辺で繋がれている頂点がないので、次数の最大値は $2$ 以上 $N-2$ 以下です。ここでその頂点を頂点 $1$ とします。

頂点 $1$ と直接繋がっていない頂点 $X$ があります。頂点 $1$ から $X$ までの距離は $2$ 以上です。頂点 $1$ の次数は $2$ 以上なので頂点 $1$ と直接繋がっている頂点で $X$ までの距離が $3$ 以上のものがあります。よって頂点 $X$ はタイプ $2$ の人に対応するものではありません。
これよりタイプ $2$ の人に対応する頂点は頂点 $1$ もしくは頂点 $1$ と直接繋がっている頂点です。ここで、タイプ $2$ の人は $3$ 人以上なので後者の頂点は $2$ つ以上あります。

ここで、先ほどと同様に頂点 $1$ と直接繋がっていない頂点 $X$ を考えると矛盾が生じます。
よって示されました。

これよりこの場合も $O(N^2)$ で解くことができます。

タイプ \(2\) の人がいない場合

全員タイプ \(3\) の人です。よって、問題は最小全域木を求める問題に帰着できるので、 \(O(N^2 \log N)\) で解くことができます。