# TANGLINGTREE - Editorial

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

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 ++
n ++
}else{
now ++
val x = (1 shl (2 * l + 1)) - 1
all.add(Triple(p,now,(1 shl (l+1)) - 1 ))
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++
generateLayer(l-1,now)
n += 3
}
}
val L = 13
repeat(3){
now ++
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.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)
}
//				"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];
ll sz[100001];
int vis=0;
void dfs(int id,int p){
vis++;
//cout << "dfs " << id << ' ' << p << endl;
int bc=0;
sz[id]=1;
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];
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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}

int tot=100000;
ll inf=1e18;
ll half=1e9;
void solve(){
vis=0;
ll wtot=inf/n;
ll mw=0;
for(int i=1; i<=n ;i++){
wtot-=w[i];mw=max(w[i],mw);
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;
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);
while(t--) solve();
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

const int N = 1E5 + 5;

int w[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);
}

// 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);
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];
}
for (int i = 1; i < n; i++) {
int u, v, r; cin >> u >> v >> 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