[BOJ] 30239 트리와 XOR - P4

문제풀이

1. 가장 작은 값을 만들려면 모두 루트와 같은 숫자로 바꿔줘야 한다. (자신 xor (자신 xor 부모) = 부모)
2. a xor (a xor b) = b인 xor의 성질을 이용한다. (자신 xor (자신 xor 부모) = 부모)
3. 루트가 1일 때의 값을 구하고 루트가 바뀔 때, 값이 어떻게 바뀌는지 관찰한다.
   루트가 A일때: Sb x (Aa xor Ab) + etc
   루트가 B일때: Sa' x (Aa xor Ab) + etc
   => 루트가 A -> B로 이동한다 하면, 루트가 B일때의 값 = 루트가 A일때의 값 + (Sa' - Sb) x (Aa xor Ab)이다. 이 때, Sa' = Sa - Sb이다.

---

주의사항

---

소요시간

1시간

---

package 백준.Platinum.P4.p30239_트리와XOR

const val MAX_N = 200000
fun main() {
    val sb = StringBuilder()
    val aArr = IntArray(MAX_N + 1)
    val sArr = IntArray(MAX_N + 1)
    val visited = BooleanArray(MAX_N + 1)
    val minPriceArr = LongArray(MAX_N + 1)
    val roadLists = List(MAX_N + 1) { mutableListOf<Int>() }
    var N = 0

    fun init() {
        for (i in 1..N) {
            roadLists[i].clear()
            sArr[i] = 0
            minPriceArr[i] = 0
        }
    }

    fun setSArr(from: Int): Int {
        visited[from] = true
        var count = 1
        for (to in roadLists[from]) {
            if (!visited[to]) count += setSArr(to)
        }
        return count.also { sArr[from] = it }
    }

    fun setSArr() {
        visited.fill(false, 1, N + 1)
        setSArr(1)
    }

    fun minPriceByRoot1(from: Int): Long {
        visited[from] = true
        var minPriceByRoot1 = 0L
        for (to in roadLists[from]) {
            if (!visited[to]) minPriceByRoot1 += (sArr[to].toLong() * (aArr[from] xor aArr[to])) + minPriceByRoot1(to)
        }
        return minPriceByRoot1
    }

    fun minPriceByRoot1(): Long {
        visited.fill(false, 1, N + 1)
        return minPriceByRoot1(1)
    }

    fun setMinPriceArr(from: Int, minPrice: Long) {
        visited[from] = true
        minPriceArr[from] = minPrice
        for (to in roadLists[from]) {
            if (!visited[to]) {
                val xor = aArr[from] xor aArr[to]
                val fromCount = sArr[from]
                val toCount = sArr[to]
                sArr[from] = fromCount - toCount
                sArr[to] = fromCount
                setMinPriceArr(to, minPrice + ((fromCount - 2 * toCount).toLong() * xor))
                sArr[from] = fromCount
                sArr[to] = toCount
            }
        }
    }

    fun setMinPriceArr(minPriceByRoot1: Long) {
        visited.fill(false, 1, N + 1)
        setMinPriceArr(1, minPriceByRoot1)
    }

    fun setResult() {
        for (i in 1..N) {
            sb.append("${minPriceArr[i]} ")
        }
        sb.appendLine()
    }

    repeat(readln().toInt()) {
        N = readln().toInt()
        init()
        readln().trim().split(" ").map(String::toInt).forEachIndexed { idx, A -> aArr[idx + 1] = A }
        repeat(N - 1) {
            val (u, v) = readln().trim().split(" ").map(String::toInt)
            roadLists[u].add(v)
            roadLists[v].add(u)
        }
        setSArr()
        setMinPriceArr(minPriceByRoot1())
        setResult()
    }
    println(sb)
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P4/p30239_%ED%8A%B8%EB%A6%AC%EC%99%80XOR/p30239_%ED%8A%B8%EB%A6%AC%EC%99%80XOR.kt

---

문제링크

https://www.acmicpc.net/problem/30239