AtCoder Beginner Contest 126 D - Even Relation

考えたこと：

・二点間についてすべて考えてしまうとＯ(N^2)で間に合わなくなる。

・距離の偶奇しか問われていないので、距離の大きさは本質ではない。

・こういう問題は根付き木にして、根を起点にして考えるとよいことが多い。

図を書いてじっと眺めてみると・・・

赤ー＞青の距離は、赤ー＞Ｙ－＞Ｘ－＞Ｙ－＞青の距離からＸ－＞Ｙを二回引いた距離

（上図黄色線）に等しい。

ここで、距離の偶奇しか本質でないことを思い出すと、往復しているＸ－＞Ｙの距離は必ず偶数になるため考えなくてもよい。（逆に言うと付け足して考えても良い）

よって、二点間の距離の偶奇は、二点間への根からの距離の和の偶奇に等しいことが示せた。

根からの各頂点の距離はＤＦＳすることでＯ(N+M)で求められる。

よって、

根からの距離が偶数の場合、０グループに

根からの距離が奇数の場合、１グループに

というふうに塗ってあげれば、題意を満たすことが出来る。

実装：

#include <bits/stdc++.h>
using namespace std;
#define int long long 

struct edge {
  int to, cost;
};
 
int N;
vector<edge> G[101010];
int d[101010];
 
void dfs(int n, int pre) {
  for (auto x : G[n]) {
    if (x.to != pre) {
      d[x.to] = d[n] + x.cost;
      dfs(x.to, n);
    }
  }
}
 
signed main() {
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    G[u].push_back({v, w});
    G[v].push_back({u, w});
  }
 
  dfs(0, -1);
 
  for (int i = 0; i < N; i++) {
    if (d[i] % 2 == 0) {
      cout << 0 << endl;
    } else {
      cout << 1 << endl;
    }
  }
 
  return 0;
}

グラフが木で、二往復することで辺上のなんらかを無視できるような問題では、根を考えることで上記のような処理が出来ることがよくあるように思う。