クリスマスツリー [yukicoder No.778] - はまやんはまやんはまやん

前提知識

解説

C(N,2)通りを全探索するのは厳しい。
なので、C(N,2)通りのうち、下にある飾りを全探索することにする。
ある頂点cuについて考えてみる。
　
クリスマスツリーは頂点0を根とした木構造となっているのだが、下の頂点をcuとして固定すると、
上の頂点として使えるのは、頂点cuの親、そのまた親、…となる。
これは「一方の飾りから上に辿るともう一方の飾りにたどり着ける。」という条件によるものである。
その中で「上にある飾りの番号が下にある飾りの番号より小さい。」を満たす頂点数がわかればいい。
　
これを実現するのにdfsとBITを使おう。
オイラーツアーの考え方に近いかもしれない。
dfsで頂点に入ったときにbit[cu] = 1として、抜けたときにbit[cu] = 0とする。
こうすると、ある頂点cuに入ったときに、その頂点と根の間の頂点についての情報がbitに反映されている。
なので、あとは集計するだけ。

int N;
vector<int> E[201010];
BIT<int> bit(201010);
//---------------------------------------------------------------------------------------------------
ll ans = 0;
void dfs(int cu, int pa = -1) {
    ans += bit.get(0, cu);
    bit.add(cu, 1);
    fore(to, E[cu]) if (to != pa) dfs(to, cu);
    bit.add(cu, -1);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N) {
        int a; cin >> a;
        E[i].push_back(a);
        E[a].push_back(i);
    }

    dfs(0);
    cout << ans << endl;
}