TANGLINGTREE - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Leung Arvin
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Dynamic Programming, Slope Trick, Small To Large

PROBLEM:

You are given an undirected tree of N nodes. A positive weight W_i is assigned to the node i for all 1 \le i \le N.

For all 1 \le j \le N-1, the j-th edge connects the nodes u_j and v_j, and has a restriction value of R_j.

An array A_1, A_2, \cdots, A_N consisting of N non-negative integers is called valid if:

  • For all 1 \le j \leq N-1, the condition A_{u_j}+A_{v_j} \le R_j holds.

The profit of a valid array A is defined as profit(A)=\sum_{i=1}^N A_i \cdot W_i

Find the maximum possible value of profit(A) for some valid array A.

EXPLANATION:

We first approach the problem with dynamic programming. I will denote R_{u, v} as the restriction on the edge connecting node u to node v. Let DP_{u, x} be the maximum profit we can get out of subtree u where A_u = x, then we have the following transition:

DP_{u, x} = W_u \cdot x + \sum_{v} \max_{i=0}^{R_{u,v} - x} DP_{v, i}

where v is looping over all direct children of u. The answer is, of course, \max_{x} DP_{1, x}.

It turns out that DP_u for every node u is a piece-wise linear concave function. We can prove this by induction.

  • For all leaves l, DP_{l, x} = W_l \cdot x, which means DP_l is just a linear function.
  • For all nodes u that is not a leave, we have:
    • DP_{v} is a piece-wise linear concave function due to the induction hypothesis.
    • \max_{i=0}^{R_{u,v} - x} DP_{v, i} is a piece-wise linear concave function (we are truncating the range of DP_v and taking the prefix max, which conserves our property).
    • W_u \cdot x + \sum_{v} max_{i=0}^{R_{u,v} - x} DP_{v, i} is piece-wise linear concave (summing up conserves the property).

This means we can use slope trick to speed up our calculations. Details of constructing slope trick is straightforward if you have prerequisite knowledge about the topic, but there are some caveats in implementation:

  • The range we’re taking the max on is up to R_{u,v} - x, which involves flipping the function and shifting it by R_{u, v}. Many data structures can support these two operations, but using std::map with an offset value as well as a flipped check is enough.
  • We need to restrict A_v to be in the range [0, MR_v], where MR_v is the minimum restriction of any edge connecting to v. One way to do this “truncation” of DP_v is as follow: if the linear function going through point MR_v has a positive slope, we add new slope points at MR_v so that the linear function going through that point has slope 0 (this equates to setting DP_{v, i} = DP_{v, MR_v} for all i > MR_v).
  • Adding two piece-wise linear concave functions require merging two slope-changing-point sets. You need to apply the small-to-large technique to merge two such sets.

TIME COMPLEXITY:

Time complexity is O(N \log^2 N) for each test case (one \log comes from the data structure, the other one comes from small-to-large).

SOLUTION:

Setter's Solution
import java.io.BufferedInputStream
import java.io.File
import java.io.PrintWriter
import java.util.*
import kotlin.system.measureTimeMillis

inline fun TIME(f:()->Unit){
    val t = measureTimeMillis {
        f()
    }
    println("$t ms")
}

object IO{
    private const val BS = 1 shl 16
    private const val NC = 0.toChar()
    private val buf = ByteArray(BS)
    private var bId = 0
    private var size = 0
    private var c = NC

    var warningActive = true
    var fakein = StringBuilder()

    private var IN: BufferedInputStream = BufferedInputStream(System.`in`, BS)
    val OUT: PrintWriter = PrintWriter(System.out)

    private val char: Char
        get() {
            while (bId == size) {
                size = IN.read(buf) // no need for checked exceptions
                if (size == -1) return NC
                bId = 0
            }
            return buf[bId++].toChar()
        }

    fun nextInt(): Int {
        var neg = false
        if (c == NC) c = char
        while (c < '0' || c > '9') {
            if (c == '-') neg = true
            c = char
        }
        var res = 0
        while (c in '0'..'9') {
            res = (res shl 3) + (res shl 1) + (c - '0')
            c = char
        }
        return if (neg) -res else res
    }
    fun nextLong(): Long {
        var neg = false
        if (c == NC) c = char
        while (c < '0' || c > '9') {
            if (c == '-') neg = true
            c = char
        }
        var res = 0L
        while (c in '0'..'9') {
            res = (res shl 3) + (res shl 1) + (c - '0')
            c = char
        }
        return if (neg) -res else res
    }
    fun nextString():String{
        val ret = StringBuilder()
        while (true){
            c = char
            if(!isWhitespace(c)){ break}
        }
        ret.append(c)
        while (true){
            c = char
            if(isWhitespace(c)){ break}
            ret.append(c)
        }
        return ret.toString()
    }
    fun isWhitespace(c:Char):Boolean{
        return c == ' ' || c == '\n' || c == '\r' || c == '\t'
    }
    fun rerouteInput(){
        if(warningActive){
            put("You forgot to disable tests you digital dummy!")
            println("You forgot to disable tests you digital dummy!")
            warningActive = false
        }
        val S = fakein.toString()
        println("Got Case ")
        println(S.take(80))
        println("...")
        IN = BufferedInputStream(S.byteInputStream(),BS)
    }
    fun takeFile(name:String){
        IN = BufferedInputStream(File(name).inputStream(),BS)
    }
}
fun put(aa:Any){ IO.OUT.println(aa)}
fun done(){ IO.OUT.close() }
fun share(aa:Any){
    if(aa is IntArray){IO.fakein.append(aa.joinToString(" "))}
    else if(aa is LongArray){IO.fakein.append(aa.joinToString(" "))}
    else if(aa is List<*>){IO.fakein.append(aa.toString())}
    else{IO.fakein.append(aa.toString())}
    IO.fakein.append("\n")
}

fun getint():Int{ return IO.nextInt() }
fun getlong():Long{ return IO.nextLong() }
fun getline(n:Int):IntArray{
    val ret = IntArray(n);repeat(n){ret[it] = getint()};return ret
}
fun getlineL(n:Int):LongArray{
    val ret = LongArray(n);repeat(n){ret[it] = getlong()};return ret
}
fun getstr():String{ return IO.nextString() }

val List<Char>.ret:String
    get() = this.joinToString("")
infix fun Any.dei(a:Any){
    //does not stand for anything it is just easy to type, have to be infix because kotlin does not have custom prefix operators
    var str = ""
    if(this is String){ str = this
    }else if(this is Int){ str = this.toString()
    }else if(this is Long){ str = this.toString()
    }
    if(a is List<*>){ println("$str : ${a.joinToString(" ")}")
    }else if(a is IntArray){ println("$str : ${a.joinToString(" ")}")
    }else if(a is LongArray){ println("$str : ${a.joinToString(" ")}")
    }else{ println("$str : $a")
    }
}
val just = " " // usage: just dei x , where x is the debug variable
fun crash(){throw Exception("Bad programme")} // because assertion does not work
fun assert(a:Boolean){
    if(!a){
        throw Exception("Failed Assertion")
    }}
enum class solveMode {
    real, rand, tc
}
const val withBruteForce = false
const val randCount = 100
object solve{
    var mode:solveMode = solveMode.real
    var tcNum:Int = 0
    var rand:()->Unit = {}
    var TC:MutableMap<Int,()->Unit> = mutableMapOf()
    var answersChecked = 0
    var tn:Long = 0
    fun cases(onecase:()->Unit){
        val t = if(mode == solveMode.real){if(singleCase) 1 else getint()} else if(mode == solveMode.tc){1 } else randCount
        //safety checks
        if(pI != 998_244_353 && pI != 1_000_000_007){
            throw Exception("Modding a wrong prime!")
        }

        if(t == 1 && mode != solveMode.real){
            tn = System.currentTimeMillis()
        }
        repeat(t){
            if(mode == solveMode.tc){
                TC[tcNum]?.let { it() }
                IO.rerouteInput()
            }else if(mode == solveMode.rand){
                rand()
                IO.rerouteInput()
            }
            currentAnswer = null
            currentBruteAnswer = null
            onecase()
        }
        if(withBruteForce){
            put("Checked ${answersChecked}")
        }
        if(t == 1 && mode != solveMode.real){
            val dt = System.currentTimeMillis() - tn
            println("Time $dt ms ")
        }
    }
    inline fun singleCase(a:solve.()->Unit){
        val t = if(mode != solveMode.rand){1} else randCount
        repeat(t) { a() }
    }
    fun rand(a:()->Unit){
        this.rand = a
    }
    fun tc(id:Int = 0,a:()->Unit){
        TC[id] = a
    }
    inline fun brute(a:()->Unit){
        if(withBruteForce){
            a()
        }
    }
    fun usetc(a:Int = 0 ){
        this.tcNum = a
        this.mode = solveMode.tc
    }
    fun userand(){
        this.mode = solveMode.rand
    }


    var currentAnswer:String? = null
    var currentBruteAnswer:String? = null
    fun answer(a:Any){
        currentAnswer = a.toString()
        if(currentBruteAnswer != null){
            checkAnswer()
        }
    }
    fun put2(a:Any){answer(a);put(a) }

    fun bruteAnswer(a:Any){
        currentBruteAnswer = a.toString()
        if(currentAnswer != null){
            checkAnswer()
        }
    }
    fun checkAnswer(){
        if(currentAnswer != currentBruteAnswer){
            throw Exception("Failed Test: BF $currentBruteAnswer Current $currentAnswer")
        }
        answersChecked ++
    }
}
// 1. Modded
const val p = 1000000007L
const val pI = p.toInt()
fun Int.adjust():Int{ if(this >= pI){ return this  - pI }else if (this < 0){ return this + pI };return this }
fun Int.snap():Int{ if(this >= pI){return this - pI} else return this}
infix fun Int.modM(b:Int):Int{ return ((this * 1L * b) % pI).toInt() }
infix fun Int.modPlus(b:Int):Int{ val ans = this + b;return if(ans >= pI) ans - pI else ans }
// 2. DP initial values
const val plarge = 1_000_000_727
const val nlarge = -plarge
const val phuge = 2_727_000_000_000_000_000L
const val nhuge = -phuge
// 3. conveniecen conversions
val Boolean.chi:Int get() = if(this) 1 else 0 //characteristic function
val Char.code :Int get() = this.toInt() -  'a'.toInt()
//3. hard to write stuff
fun IntArray.put(i:Int,v:Int){ this[i] = (this[i] + v).adjust() }
val mint:MutableList<Int> get() = mutableListOf<Int>()
val mong:MutableList<Long> get() = mutableListOf<Long>()



// convert all to 0 based

fun Tree(n:Int):Graph{
    val G = Graph(n,false)
    repeat(n-1){
        G.add(getint()-1, getint() - 1)
    }
    return G
}
class Graph(val n:Int, val directed:Boolean){
    // Small graph, 1 sec , 40M, flow stuff is fast
    // Big graph , 1 sec, ~ 1.7M
    val E = Array<MutableList<Int>>(n) { mutableListOf() }
    val indices = 0 until n
    val lastIndex get() = n- 1
    fun add(a:Int,b:Int){
        E[a].add(b)
        if(!directed){
            E[b].add(a)
        }
    }
    inline fun NS(from:Int,act:(Int)->Unit){
        for(v in E[from]){
            act(v)
        }
    }
    inline fun everyEdge(act:(Int,Int)->Unit){
        for((i,v) in E.withIndex()){
            for(to in v){
                if(directed || i < to){
                    act(i,to)
                }
            }
        }
    }

    inline fun BFS(root:Int,reached:(Int,Int)->Unit): IntArray {
        val toDo = ArrayDeque<Int>()
        val explored = IntArray(n+1){-1} // also store parents
        toDo.add(root)
        explored[root] = -2
        val dist = IntArray(n){-1}
        dist[root] = 0

        while(toDo.size > 0){
            val x = toDo.removeFirst()
            reached(x,explored[x])
            NS(x){ a->
                if(explored[a] == -1){
                    explored[a] = x
                    dist[a] = dist[x] + 1
                    toDo.addLast(a)
                }
            }
        }
        return dist
    }
    val basic_active = true
    val basic_setup = if(basic_active) n else 0

    val parent = IntArray(basic_setup)
    val depth = IntArray(basic_setup)
    val sizes = IntArray(basic_setup)
    val subs = List(basic_setup){mutableListOf<Int>()}
    fun setup(){
        if(!basic_active){
            println("Did not set basic setup ")
        }
        val root = 0
        DFS_long(root,{ v ->
            sizes[v]++
            if(v != root) sizes[parent[v]] += sizes[v]
        }){
                from,to ->
            parent[to] = from
            depth[to] = depth[from] + 1
            subs[from].add(to)
        }
        parent[root] = -1
    }
    inline fun DFS(dfsOrder:(Int)->Unit){
        DFS_long(0,dfsOrder,{_,_->})
    }
    inline fun DFS_long(root:Int,dfsOrder:(Int)->Unit,long:(parent:Int,here:Int)->Unit){
        //Long: (from,to) i.e. (parent, child)
        var pointer = 0
        val toDo = IntArray(n+1)

        val explored = BooleanArray(n+1)
        val secondTime = BooleanArray(n+1)
        toDo[0] = root
        explored[root] = true

        while(pointer >= 0){
            val x = toDo[pointer]
            if(secondTime[x]){
                dfsOrder(x)
                pointer--
                continue
            }
            //move here for top down order
            secondTime[x] = true
            NS(x){ a->
                if(!explored[a]){
                    explored[a] = true
                    pointer++
                    long(x,a)
                    toDo[pointer] = a
                }
            }
        }
    }
    inline fun DFS_Long_Exhaust(dfsOrder:(Int)->Unit,newroot:(Int)->Unit = {},long:(p:Int,into:Int,root:Int)->Unit = {_,_,_ ->}){
        //Long: (from,to) i.e. (parent, child)
        var pointer:Int
        val toDo = IntArray(n)

        val explored = BooleanArray(n)
        val secondTime = BooleanArray(n)

        var exploredCount = 0
        var exploredPointer = 0

        while(exploredCount < n){
            while(explored[exploredPointer]){
                exploredPointer ++
            }
            val root = exploredPointer
            newroot(root)
            explored[root] = true
            exploredCount ++
            toDo[0] = root
            pointer = 0
            while(pointer >= 0){
                val x = toDo[pointer]
                if(secondTime[x]){
                    dfsOrder(x)
                    pointer--
                    continue
                }
                //move here for top down order
                secondTime[x] = true
                NS(x){ a->
                    if(!explored[a]){
                        explored[a] = true
                        exploredCount ++
                        pointer++
                        long(x,a,root)
                        toDo[pointer] = a
                    }
                }
            }
        }
    }
}
inline fun product(a:List<Int>,act:(List<Int>)->Unit){
    val current = MutableList(a.size){0}
    while(true){
        act(current)
        val lastGood = (0 until a.size).lastOrNull{a[it]-1 != current[it]}
        if(lastGood == null){
            return
        }
        current[lastGood] += 1
        for(i in lastGood+1 until a.size){
            current[i] = 0
        }
    }
}

data class edge(val x:Int, val y:Int, val r:Int)

class StrongSlopeTrick(var min:Long, var max:Long,val slopes:TreeMap<Long,Long>){
    var startF = 0L
    var endF = 0L
    var startslope = 0L
    var endslope = 0L
    var inverted = false // if inverted,
    var shift = 0L

    val size:Int get() = slopes.size

    fun output(){
        println()
        var f = startF
        var slopenow = startslope
        fun doit(i:Long){
            if(i != min) f += slopenow
            slopenow += slopes.getOrDefault(if(!inverted)(i - shift) else (shift - i),0)
            i dei f
        }
        for(i in min..max){
            doit(i)
        }
        assert(endF == f)
        assert(endslope == slopenow)
    }
    fun softOutput(){
        var f = startF
        var slopenow = startslope
        println()
        var last = min
//		var last = if(!inverted) min else max
        last dei f
        for((i,v) in slopes.entries){
            val here = if(!inverted) (i + shift) else (shift -i)
            f += slopenow * (here - last)
            slopenow += v

            here dei f

            last = here
        }
        f += slopenow * (max - last)
        max dei f
//		(if(!inverted) max else min)  dei f
        assert(f == endF)
        assert(slopenow == endslope)

//		}

    }

    fun shiftRight(a:Long):StrongSlopeTrick {
        val new = StrongSlopeTrick(min+a,max+a,slopes)
        new.startF = startF
        new.endF = endF
        new.startslope = startslope
        new.endslope = endslope
        new.inverted = inverted
        new.shift += shift + a
        return new
    }
    fun reverse():StrongSlopeTrick{
        // f [min,max] -> something , becomes f[-max,-min] -> same values

        // rememrbet he set is ocnsistent
        val new = StrongSlopeTrick(-max, -min,slopes)
        new.startF = endF
        new.endF = startF
        new.startslope = -endslope
        new.endslope = -startslope
        new.inverted = !inverted
        new.shift = -shift

        return new
//		return
    }
    fun rangeAdd(x:Long, s:Long){

        //mutating
        //effectively: range add from x to max by s

        // range add 0,0,0,0,0, -s, -2s, ....
//		assert(s <= 0)
        if(x in min.. max){
            val len = (max -x)
            endF += len  * s
            endslope += s
            val newpos = if(!inverted) (x- shift) else (shift - x )
            val new = slopes.getOrDefault(newpos,0L) + s
            if(new != 0L){
                slopes[newpos] = new
            }else{
                slopes.remove(newpos)
            }

        }else if(x < min){
            addLinear(x,s)
        }

    }
    fun toMapPosition(x:Long):Long {
        return if(!inverted) (x- shift) else (shift - x )
    }
    fun toRealPosition(map:Long):Long{
        return if(!inverted) (map + shift) else (shift -map)
    }
    fun addLinear(zero:Long, m:Long){
        startslope += m
        endslope += m
        endF += m * (max-zero)
        startF += m * (min-zero)
    }
    fun addConstant(a:Long){
        startF += a
        endF += a
    }
    fun extendTo(x:Long){
        assert(endslope >= 0)
        rangeAdd(max,-endslope)
        max = x
    }
    fun restrictTo(x:Long){
        assert(x >= min)
        while(slopes.isNotEmpty()){
            val last = if(!inverted) slopes.lastEntry() else slopes.firstEntry()
            val pos = toRealPosition(last.key)
            if(pos >= x){
                rangeAdd(pos,-last.value)
            }else{
                break
            }
        }
        val dif = max - x
        endF -= (dif * endslope)
        max = x
    }
    fun takePrefixMax(){
        while(slopes.isNotEmpty() && endslope < 0){
            val last = if(!inverted) slopes.lastEntry() else slopes.firstEntry()
            val adjust = minOf(-last.value,-endslope)
            rangeAdd(toRealPosition(last.key),adjust)
        }
        if(slopes.isEmpty() && endslope < 0){
            addLinear(min,-startslope)
        }
    }
    fun addContenstOf(other:StrongSlopeTrick) {
        assert(min >= other.min && max <= other.max)

        addConstant(other.startF)
        addLinear(other.min,other.startslope)
        for((i, v) in other.slopes.entries) {
            val here = if(!other.inverted) (i + other.shift) else (other.shift - i)
            rangeAdd(here, v)
            mergecount ++
        }
    }
}

var mergecount = 0
const val singleCase = false
fun main(args: Array<String>) {
//	val A = StrongSlopeTrick(0,5,TreeMap())
//	A.addLinear(0,3)
//	A.rangeAdd(2,-1)
//	A.takePrefixMax()
//	A.output()
//	solve.tc {
//		val n = 100000
//		share(n)
//		share(List(n){9000000+Random.nextInt(1..100000)})
//		for(i in 2..n){
//			share("$i ${i/2} ${2 * n- i + 3 }")
//		}
//	}
    solve.tc(2){
        var n = 1
        var now = 1
        val ret = mutableListOf<Int>()
        val all = mutableListOf<Triple<Int,Int,Int>>()
        fun generateLayer(l:Int, p:Int){
            if(l == 0){
                now ++
                all.add(Triple(p,now,1))
                n ++
                ret.add(1)
            }else{
                now ++
                val x = (1 shl (2 * l + 1)) - 1
                all.add(Triple(p,now,(1 shl (l+1)) - 1 ))
                ret.add(x)
                generateLayer(l-1,now)
                now ++
                all.add(Triple(p,now,(1 shl (l+1)) - 1 ))
                all.add(Triple(now,now+1,(1 shl (l+1)) - 1 ))
                now++
                ret.add(x)
                ret.add(x shr 1)
                generateLayer(l-1,now)
                n += 3
            }
        }
        val L = 13
        ret.add(1 shl 27)
        repeat(3){
            now ++
            ret.add(1 shl (2* L +2))
            all.add(Triple(1,now,(1 shl (L+1)) - 1 ))
            generateLayer(L,now)
        }


//		println("vertex count : $n")
        share(now)
        share(ret.joinToString(" "))

        for(a in all){
            share("${a.first} ${a.second} ${a.third }")
        }

    }
    solve.tc(3){
        share(6)
        share(intArrayOf(15,7,3,7,1,1))
        share("1 2 2")
        share("2 3 2")
        share("1 4 2")
        share("4 5 1")
        share("3 6 1")
//		share("1 2 4")
//		share("2 3 2")
//		share("3 4 1")
//		share("1 5 4")
//		share("5 6 4")
//		share("6 7 2")
//		share("7 8 1")
    }
//	solve.usetc(2)
    solve.cases{
        val n = getint()
        val W = getline(n)
        val all = List(n-1){
            edge(getint() - 1, getint() - 1 , getint() )
        }
        val G = Graph(n,false)
        for(e in all){
            G.add(e.x, e.y)
        }
        G.setup()

        val bestweights = IntArray(n){Int.MAX_VALUE}
        var restrictions = IntArray(n)
        restrictions[0] = 0

        for(e in all){
            bestweights[e.x] = minOf(bestweights[e.x],e.r)
            bestweights[e.y] = minOf(bestweights[e.y], e.r)
            if(G.depth[e.x] < G.depth[e.y]){
                restrictions[e.y] = e.r
            }else{
                restrictions[e.x] = e.r
            }
        }
//		println(1.0 * W.maxOrNull()!! * all.maxOf{it.r} * n)
        var max = 0L

        val DP = Array<StrongSlopeTrick?>(n){null }

        G.DFS {v ->
            val max = bestweights[v].toLong()
            var best:StrongSlopeTrick? =null
            var r = -1L
            var opt = -1
            for(w in G.subs[v]){
                if(best == null || best.size < DP[w]!!.size){
                    best = DP[w]!!
                    r = restrictions[w].toLong()
                    opt = w
                }
            }
            if(best == null){
                best = StrongSlopeTrick(0,max,TreeMap())
            }else{
                if(best.max <= r){
                    best.extendTo(r)
                }
                best = best.reverse().shiftRight(r)
            }
            if(best.max > max){
                best.restrictTo(max)
            }
            for(w in G.subs[v]) {
                if(w == opt) continue
                val other = DP[w]!!
                val rr = restrictions[w].toLong()
                if(other.max <= rr) {
                    other.extendTo(rr)
                }
                best.addContenstOf(other.reverse().shiftRight(rr))
//				"merge $v" dei other.size
            }
            DP[v] = best
            best.addLinear(0,W[v].toLong())
            best.takePrefixMax()

//			println(v)
//			best.output()

//			best.softOutput()
//			println(best.size)
        }
//		println("Merged: $mergecount")
        put(DP[0]!!.endF)

//		val DP = Array(n){LongArray(0)}
//		G.DFS {v ->
//			val max = bestweights[v]
//			DP[v] = LongArray(1 + max){1L * W[v] * it}
//			for(w in G.subs[v]){
//				for(i in 0..max){
//					DP[v][i] += DP[w][minOf(bestweights[w],restrictions[w] - i)]
//				}
//			}
//			for(i in 0 until max){
//				DP[v][i+1] = maxOf(DP[v][i+1], DP[v][i])
//			}
//		}
//		put(DP[0].last())
    }
    done()
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
int n;
ll w[100001],r[100001];
map<ll,ll>s[100001],t[100001];
ll a[100001],b[100001];
ll f0[100001],fr[100001];
vector<pair<ll,int> >adj[100001];
ll sz[100001];
int vis=0;
void dfs(int id,int p){
	vis++;
	//cout << "dfs " << id << ' ' << p << endl;
	int bc=0;
	sz[id]=1;
	for(auto c:adj[id]){
		if(c.se==p) continue;
		dfs(c.se,id);
		sz[id]+=1;
		if(s[c.se].size()>s[bc].size()) bc=c.se;
		int cur=c.se;
		ll tot=0;
		while(true){
			ll x=-(t[cur].begin()->fi+b[cur]);
			if(x<=c.fi) break;
			tot+=s[cur][x+a[cur]];
			fr[cur]-=tot*(x-c.fi);
			t[cur].erase(-x-b[cur]);
			s[cur].erase(x+a[cur]);
		}
		s[cur][c.fi+a[cur]]+=tot;
		t[cur][-c.fi-b[cur]]+=tot;
		//cout << "!!! " << id << ' ' << c.se << ' ' << c.fi << ' ' << r[id] << endl;
		tot=2e9;
		f0[cur]+=tot*(c.fi-r[id]);
		while(true){
			ll x=(s[cur].begin()->fi-a[cur]);
			if(x>=c.fi-r[id]) break;
			tot-=s[cur][x+a[cur]];
			//cout << "hello " << id << endl;
			f0[cur]-=s[cur][x+a[cur]]*((c.fi-r[id])-x);
			t[cur].erase(-x-b[cur]);
			s[cur].erase(x+a[cur]);	
		}
		s[cur][c.fi-r[id]+a[cur]]+=2e9-tot;
		t[cur][-(c.fi-r[id])-b[cur]]+=2e9-tot;
		
		a[cur]+=c.fi-r[id];
		b[cur]+=c.fi-r[id];
	}
	if(bc==0){
		f0[id]=0;fr[id]=r[id]*w[id];
		s[id][0]+=2e9-w[id];
		s[id][r[id]]+=w[id];
		t[id][0]+=2e9-w[id];
		t[id][-r[id]]+=w[id];
		a[id]=b[id]=0;
		return;
	}
	//cout << "hello " << id << ' ' << r[id] << endl;;
	a[id]=-b[bc]-r[id];
	b[id]=-a[bc]-r[id];
	s[id].swap(t[bc]);
	t[id].swap(s[bc]);
	f0[id]=fr[bc];
	fr[id]=f0[bc];
	for(auto d:adj[id]){
		if(d.se==p || d.se==bc) continue;
		auto c=d.se;
		for(auto it:s[c]){
			ll x=it.fi-a[c];//old x
			x=r[id]-x;//new x
			t[id][-x-b[id]]+=it.se;
		}
		for(auto it:t[c]){
			ll x=-(it.fi+b[c]);
			x=r[id]-x;
			s[id][x+a[id]]+=it.se;
		}
		f0[id]+=fr[c];
		fr[id]+=f0[c];
	}
	s[id][a[id]]+=2e9-w[id];
	s[id][r[id]+a[id]]+=w[id];
	t[id][-b[id]]+=2e9-w[id];
	t[id][-b[id]-r[id]]+=w[id];
	fr[id]+=w[id]*r[id];
	ll heal=((ll)(2e9))*(sz[id]-1);/*
	cout << "tmp " << id << endl;
	cout << f0[id] << ' ' << fr[id] << endl;
	cout << "S: " << endl;
	for(auto c:s[id]){
		cout << c.fi-a[id] << ' ' << c.se << endl;
	}
	cout << "T: " << endl;
	for(auto c:t[id]){
		cout << -(c.fi+b[id]) << ' ' << c.se << endl;
	}
	cout << endl*/
	while(true){
		ll x=-(t[id].begin()->fi+b[id]);
		if(s[id][x+a[id]]>heal){
			s[id][x+a[id]]-=heal;
			t[id][-x-b[id]]-=heal;
			fr[id]+=heal*(r[id]-x);
			break;
		}
		heal-=s[id][x+a[id]];
		fr[id]+=s[id][x+a[id]]*(r[id]-x);
		s[id].erase(x+a[id]);
		t[id].erase(-x-b[id]);
	}/*
	cout << "res " << id << endl;
	cout << f0[id] << ' ' << fr[id] << endl;
	cout << "S: " << endl;
	for(auto c:s[id]){
		cout << c.fi-a[id] << ' ' << c.se << endl;
	}
	cout << "T: " << endl;
	for(auto c:t[id]){
		cout << -(c.fi+b[id]) << ' ' << c.se << endl;
	}
	cout << endl;*/
}
long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

int tot=100000;
ll inf=1e18;
ll half=1e9;
void solve(){
	n=readIntLn(3,tot);tot-=n;
	vis=0;
	ll wtot=inf/n;
	ll mw=0;
	for(int i=1; i<=n ;i++){
		if(i!=n) w[i]=readIntSp(1,min(wtot,half));
		else w[i]=readIntLn(1,min(wtot,half));
		wtot-=w[i];mw=max(w[i],mw);
		adj[i].clear();
		s[i].clear();t[i].clear();
		r[i]=1e18;
	}
	ll rmax=inf/n/mw;
	for(int i=1; i<n ;i++){
		int u,v;ll z;
		u=readIntSp(1,n);
		v=readIntSp(1,n);
		z=readIntLn(1,min(rmax,half));
		adj[u].push_back({z,v});
		adj[v].push_back({z,u});
		r[u]=min(r[u],z);
		r[v]=min(r[v],z);
	}
	dfs(1,0);
	assert(vis==n);
	cout << fr[1] << '\n';
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int t;t=readIntLn(1,100000);
    while(t--) solve();
    readEOF();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

const int N = 1E5 + 5;

int w[N];
vector<pair<int, int>> adj[N];

struct slope_trick {
    long long a_left, b_left;
    long long a_right, b_right;
    long long offset;
    bool flipped;
    map<long long, long long> points;

    slope_trick(int w) {
        a_left = w; b_left = 0;
        a_right = w; b_right = 0;
        offset = 0;
        flipped = false;
    }

    long long to_real_point(long long x) const {
        return (flipped ? -1 : 1) * x + offset;
    }

    long long to_fake_point(long long x) const {
        return (x - offset) * (flipped ? -1 : 1);
    }

    void add_constant(long long c) {
        // ax + b = a(c + x) + (b - ac)
        b_left -= c * a_left; b_right -= c * a_right;
        offset += c;
    }

    void flip() {
        // ax + b = (-a) * (-x) + b
        swap(a_left, a_right); swap(b_left, b_right);
        a_left *= -1; a_right *= -1;
        offset *= -1; flipped = !flipped;
    }

    long long get(bool left) {
        if (left ^ flipped) {
            return points.begin()->first;
        } else {
            return prev(points.end())->first;
        }
    }

    void truncate(int r) {
        while (!points.empty() && to_real_point(get(false)) >= r) {
            long long rightmost = get(false);
            long long x = to_real_point(rightmost);
            b_right -= points[rightmost] * x; a_right += points[rightmost];
            points.erase(rightmost);
        }
        if (a_right > 0) {
            points[to_fake_point(r)] += a_right;
            b_right += a_right * r; a_right = 0;
        }
    }

    void prefix_maximize() {
        while (a_left > 0) {
            long long leftmost = get(true);
            long long sub = min(a_left, points[leftmost]);
            b_left += sub * to_real_point(leftmost); a_left -= sub;
            if ((points[leftmost] -= sub) == 0) {
                points.erase(leftmost);
            }
        }
    }

    slope_trick &operator+=(const slope_trick &oth) {
        a_left += oth.a_left; b_left += oth.b_left;
        a_right += oth.a_right; b_right += oth.b_right;
        for (auto [x, occ] : oth.points) {
            points[to_fake_point(oth.to_real_point(x))] += occ;
        }
        return *this;
    }
};

slope_trick DFS(int u, int ri = numeric_limits<int>::max(), int p = 0) {
    slope_trick ans = slope_trick(w[u]);
    for (auto [v, rs] : adj[u]) {
        if (v != p) {
            slope_trick ch = DFS(v, rs, u);
            ch.flip(); ch.add_constant(rs); ch.prefix_maximize();
            if (ans.points.size() < ch.points.size()) {
                swap(ans, ch);
            }
            ri = min(ri, rs);
            ans += ch;
        }
    }
    ans.truncate(ri);
    return ans;
}

long long solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        adj[i].clear();
    }
    for (int i = 1; i < n; i++) {
        int u, v, r; cin >> u >> v >> r;
        adj[u].push_back({v, r});
        adj[v].push_back({u, r});
    }
    slope_trick ans = DFS(1);
    ans.prefix_maximize();
    return ans.b_left;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        cout << solve() << '\n';
    }
}
2 Likes