E. Sagheer and Apple Tree [Codeforces Round #417 (Div. 2)] - はまやんはまやんはまやん

http://codeforces.com/contest/812/problem/E

問題概要

N頂点の根が頂点1の木がある。
各頂点にはりんごの個数A[i]が書いてある。
根からどの葉への距離は全ての葉に対してパリティが一致する（偶奇が一致する）
以下のようにゲームを行うとする

ある葉から任意個のりんごを選んで取る
ある葉以外から任意個のりんごを取って、その子供のうちいずれかに置く
上記の操作のどちらかを行うとして、どちらも行えなくなったら負け
相手が先手

ゲームをする前に1回だけ任意の2つの頂点のりんごの個数を入れ替える。
どちらも最適に行動するとして、自分が勝てるようにする入れ替えのパターン数は？

必要知識

解法

http://codeforces.com/contest/812/submission/27535775
まず、りんごを入れ替えないとして考えてみる。
結論から言うと、このゲームは葉から数えて偶数番目にある頂点のりんごのみを使ったNimに帰着できる。
子供にりんごを渡す操作は相手が行った場合はそれを打ち消すように自分がそのりんごを更に子に動かせば状態が保たれる。
あとは、頑張ってNimを計算してやればいいのだが、今回は入れ替えのパターン数について聞かれている。

まず、現在の状態で偶数番目のりんごの数のxor和を取った時に==0と!=0の時で処理を分ける。
==0の場合
この時は、既に自分が勝てる状態にあるので、これを崩さないような入れ替えが答えになる。
これは、偶数番目同士の入れ替えか奇数番目同士の入れ替えである。
なので、それぞれの頂点数を数えてnC2みたいに計算すればいい。

!=0の場合
この時は、自分が負け状態にあるので、適切に入れ替えることでxor和を0にしたい。
偶数番目のりんごの個数について全探索する。
そのりんごの個数を抜いて(xorA[i])できるxor和とxorして0になる奇数番目のりんごの個数を数え上げていけばいい。
これはmapなどを使えば簡単にできる。

var sc = FastScanner()
var pw = PrintWriter(System.out)

var N = 0
var A :Array<Int> = arrayOf()
var E :MutableList<MutableList<Int>> = mutableListOf()
var D :MutableList<Int> = mutableListOf()

var EVEN :MutableList<Int> = mutableListOf()
var ODD :MutableMap<Int,Int?> = mutableMapOf()
var EN:Long = 0
var EO:Long = 0

fun dfs(cu: Int, pa: Int):Int {
    var x = 0
    E[cu].forEach {
        if(it == pa) return@forEach
        x = x xor dfs(it, cu)
        D[cu] = D[it] + 1
    }
    if(D[cu] % 2 == 0) {
        x = x xor A[cu]
        EVEN.add(A[cu])
        EN++
    } else {
        if(!ODD.containsKey(A[cu])) ODD[A[cu]] = 0
        var y :Int = ODD[A[cu]]!!
        ODD[A[cu]] = y + 1
        EO++
    }
    return x
}

fun main(args: Array<String>) {
    N = sc.nextInt()
    A = Array(N, { i -> sc.nextInt()})

    for(i in 0 until N) E.add(mutableListOf())
    for(i in 1 until N) {
        var j = sc.nextInt() - 1
        E[i].add(j)
        E[j].add(i)
    }
    for(i in 0 until N) D.add(0)

    var x = dfs(0, -1)
    
    var ans:Long = 0
    for (i in EVEN) {
        var xx = x xor i
        if(!ODD.containsKey(xx)) continue
        var cnt:Int = ODD[xx]!!
        ans += cnt.toLong()
    }
    if(x == 0) {
        ans += EN * (EN - 1L) / 2L
        ans += EO * (EO - 1L) / 2L
    }
    println(ans)

}