AtCoder Beginner Contest 126 D - Even Relation

問題

atcoder.jp

考察と解法

世の中には2種類の頂点が存在する。白色の頂点と黒色の頂点である。

by トコロテン

はい、そうですかといった感じですね。

さて、今回の問題を整理すると以下のようになります。

• N個の頂点を持つ重み付きの木構造のデータが入力として与えられる。
• 同色の任意の2頂点の距離が偶数であるという条件の下、各頂点に白か黒の色を塗る。

2頂点の距離というのは、ある頂点から別の頂点へ移動する際に通る辺の重みの総和の最小値になります。

入力とそれに対応する解のイメージとしては以下の図のような感じです。ある解の各頂点の色を反転させたものもまた解となります。

例を確認したところで考察をしていきます。 考察するにあたって、以下の2つの関数を定義します。 $$ dist(a, b) := 頂点a, b間の距離 \\ color(v) = \left\{ \begin{array}{} 0 & (頂点vが白) \\ 1 & (頂点vが黒) \end{array} \right. $$

まずはじめに、任意の頂点Sを1つ選び、頂点sに色を塗ってみます。 この際、塗る色は白と黒のどちらでもいいはずです。 なぜならば、上でも説明した通り、ある解の各頂点の色を反転させたものもまた解となるため、ある頂点が白なのか黒なのかは本質ではなく、どの頂点とどの頂点が同じ色なのかということのみが重要だからです。

解の条件 $$ color(a) = color(b) \Rightarrow dist(a, b) \equiv 0 \bmod 2 $$

の対偶をとると以下のようになります。 $$ dist(a, b) \equiv 1\bmod 2 \Rightarrow color(a) \neq color(b) $$

したがって、の色がに決定します。

では、反対にとした時にについてとしてよいのかといった疑問が残ります。 これは結論からするとしてよいです。

以下を示します。 $$ dist(e_1, e_2) \equiv 0\bmod 2 (\forall e_1, e_2 \in E) $$

まず、sを木の根とし、とを達成する経路上でから根の方向に向かって初めに合流する点をとします。

この時、 $$ dist(e_1, e_2) = dist(e_1, s) + dist(e_2, s) - 2 * dist(v_p, s) \\ $$

となります。また、 $$ dist(e_1, s) \equiv 0\bmod 2 \\ dist(e_2, s) \equiv 0\bmod 2 \\ 2 * dist(v_p, s) \equiv 0\bmod 2 $$

であるから、 $$ dist(e_1, s) + dist(e_2, s) - 2 * dist(v_p, s) \equiv 0 \bmod 2 $$ が成立します。

したがって、 についてとしてよいです。 これによって、頂点sを1つ選ぶことで残りの全ての頂点の色が頂点sとの距離の偶奇によって決定できることがわかりました。 特に、とすることで任意の頂点vについて以下が成立します。 $$ color(v) = dist(s, v) \bmod 2 $$

以上を踏まえて、アルゴリズムの計算量を見積もります。

計算量

適当な頂点を1つ選びそこから全ての頂点への距離を求めればよいため、計算量はとなります。

実装上の注意点

木を表現するにあたって、頂点間の辺の接続情報を隣接行列で表現しようとすると各頂点について接続されている遷移先の頂点を調べるのにかかり、全体の計算量がになってしまいます。 したがって、辺の接続情報は工夫して保持しましょう。具体的な実装方法は以下のコードを見てください。

ソースコード

#include <iostream>
#include <vector>
 
using namespace std;
 
void set_color(int node, int color, vector<vector<pair<int, int> > >& edges, vector<bool>& hasVisited, vector<int>& colors)
{
    colors[node] = color;
    hasVisited[node] = true;
 
    for(auto edge : edges[node])
    {
        int next_node = edge.first;
        int cost = edge.second;
        if(!hasVisited[next_node])
        {
            set_color(next_node, (color + cost) % 2, edges, hasVisited, colors);
        }
    }
}
 
int main()
{
    int n;
    vector<vector<pair<int, int> > > edges;
    vector<bool> hasVisited;
    vector<int> colors;
 
    cin >> n;
 
    edges.resize(n + 1);
    hasVisited.resize(n + 1, false);
    colors.resize(n + 1);
 
    for(int i = 0; i < n - 1; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back(make_pair(v, w));
        edges[v].push_back(make_pair(u, w));
    }
 
    set_color(1, 0, edges, hasVisited, colors);
 
    for(int i = 1; i <= n; ++i)
    {
        cout << colors[i] << endl;
    }
 
    return 0;
}

感想

木の気持ちになることが大切な気がします。木だけにってね🤗