四边形不等式 对于一个代价函数 $w(l,r)$，如果对于任意的 $a\le b\le c\le d$，都满足： w(a,c)+w(b,d)≤w(a,d)+w(b,c)w(a,c)+w(b,d)\le…

前言 本文用于纪念自己过掉的第三道黑题（雾 前置芝士 树形 DP，树上背包 向量 凸包与闵可夫斯基和 差分 平衡树 题目大意 给定一棵 $n$ 个节点的带权无根树，节点编号 $1\sim n$。从中选…