GardlandRec.kt

import kotlin.coroutines.*
import kotlin.coroutines.intrinsics.*

// Solution for http://codeforces.com/problemset/problem/767/C
fun main() {
    val n = readLine()!!.toInt()
    val a = IntArray(n + 1)
    val t = IntArray(n + 1)
    for (i in 1..n) {
        val (ai, ti) = readLine()!!.split(" ").map { it.toInt() }
        a[i] = ai
        t[i] = ti
    }
    println(solveGarlandRec(a, t)?.joinToString(" ") ?: "-1")
}

fun solveGarlandRec(a: IntArray, t: IntArray): List<Int>? {
    val total = t.sum()
    if (total % 3 != 0) return null
    val children = a.asSequence().withIndex().drop(1).groupBy({ it.value }, { it.index })
    val expected = total / 3
    val result = ArrayList<Int>()

    suspend fun Rec.dfs(i: Int): Int {
        var iSum = t[i]
        val list = children[i] ?: return iSum
        for (j in list) {
            val jSum = rec { dfs(j) }
            if (jSum == expected && result.size < 2) {
                result += j
            } else {
                iSum += jSum
            }
        }
        return iSum
    }

    Rec { dfs(children.getValue(0).single()) }
    return result.takeIf { it.size == 2 }
}

@RestrictsSuspension
class Rec(block: suspend Rec.() -> Unit) {
    private var cur: (() -> Unit)? = null

    init {
        var ex: Throwable? = null
        block.startCoroutine(this, Continuation(EmptyCoroutineContext) { ex = it.exceptionOrNull() })
        while (true) { cur?.invoke() ?: break }
        ex?.let { throw it }
    }

    suspend fun <T> rec(block: suspend Rec.() -> T): T = suspendCoroutineUninterceptedOrReturn { cont ->
        cur = { block.startCoroutine(this, cont) }
        COROUTINE_SUSPENDED
    }
}