- https://www.spoj.com/problems/COT6/
- https://github.com/lychees/ACM-Training/tree/master/Archive/Spoj/COT%20%E7%B3%BB%E5%88%97/COT6
前排膜拜主席。。。
算法一：李超线段树 + 线段树合并
DP 结构和 COT3 一样，方程和 Cash 一样，都是动态维护凸壳，询问与某个向量的点积的最小值。。。
后来我系统的学习了一下 线段树合并，
然后发现有一个题的做法是李超线段树 + 线段树合并，来搞树上 dp。。。
这个题的方程和那个题差不多。。。询问向量都是 (x, 1)，所以用 kx+b 来搞更方便。。。
可以预处理出所有的 sw，来做离散化，然后打标记只要整体平移 b，不会影响线段树的结构。。。
然后就没有然后了。。。复杂度 O(nlog2n)。。。
经过这个题我们发现。。线性分段函数极值 和 动态凸包 问题是等价的。。
根据情况可以互相转换。。看怎么写好写。。。
似乎还有一种 O(nlogn) 的做法。。。dfs 序 + cdq 分治。。。（尝试了一下失败了，原因是 cdq 分治两边的状态会互相依赖。。。）
晚上再试试。。。
我发现之前的模板里有一个 bug 的地方（我靠居然连 COT6 的样例都过不去。。）
if (T[x].y(ml) > t.y(ml) || T[x].y(mr) > t.y(mr)) swap(T[x], t); //!
就是上面这行，必须要两边都检查一次，否则有可能恰好在边界，然后又相等的话，我这种写法就炸了。。。。
算法二：平衡树维护凸壳 + 启发式合并
https://t.me/TwilightParliament/102671
平衡树有很多写法。。。如果选择 Splay 的话，复杂度可以变成 O(nlogn) 。。。Splay 有着许多非常神奇的性质。。
比如 Dynamic Finger Property 。。。
对于 n>=m，把 m 个有序的元素按顺序插到一个已经有 n 个元素的 Splay 里。。
时间复杂度是 O(mlog(n/m))。。。
一通计算，可以证明启发式合并 n 个东西 from scratch 的总开销是 O(nlogn)。。
（在 n 个元素里顺序访问 m 个的总开销差不多就是把 n 分成 m 个数的和，log 以后加起来。
根据log的凹性，最差的情况是 m 个都是 n/m。。。）
不过我试图找以前自己的 Splay 维护凸壳的模板。。。交以前的题居然 WA 了。。。于是去搜了一下看看大家现在是怎么做的。。。
于是 找到了一份非常短的 Multiset 维护凸壳的代码。。。。。
考据了一下。。来自 CF 的某个瑞典的 IGM 选手 simonlindholm。。
模板仓库在 这里。。。
个人感觉这份代码实现的非常优秀。。。特别是插入过程。。。比 CLJ 的版本 都要短好多。。。
这个是一堆线性函数求极值的。。然后 p 维护的是相邻直线的交点。。。
查询的时候直接用 p 去二分查找就可以了。。。
只要对每个凸壳整体打标记，然后把模板从求最大改成求最小就可以通过了。。
const int N = int(1.2e6) + 9;
#define ll LL
struct Line {
mutable ll k, m, p;
ll eval (ll x) { return k*x+m; }
bool operator<(const Line& o) const { return k > o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LC : multiset<Line,less<> > {
const ll inf = LLONG_MAX;
LL up;
ll div(ll a, ll b) { return a/b - ((a^b) < 0 && a%b); }
ll bet(const Line& x, const Line& y) {
if (x.k == y.k) return x.m <= y.m ? inf : -inf;
return div(y.m-x.m, x.k-y.k);
}
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = inf; return 0; }
x->p = bet(*x,*y); return x->p >= y->p;
}
void add(ll k, ll m) {
m -= up;
auto z = insert({k,m,0}), y = z++, x = y;
while (isect(y,z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y=erase(y));
while ((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return l.k*x+l.m + up;
}
} H[N]; int HH[N];
const int NN = N * 20;
int n;
VI adj[N]; LL sw[N], dp[N]; int sz[N];
#define hu H[HH[u]]
#define hv H[HH[v]]
void dfs(int u,int p) {
sw[u] += sw[p];
sz[u] = 1;
LL s = 0; int max_sz = 0, vv = 0;
for (auto v: adj[u]) if (v != p) {
dfs(v, u);
s += dp[v]; sz[u] += sz[v];
if (checkMax(max_sz, sz[v])) vv = v;
}
if (max_sz) {
HH[u] = HH[vv];
hu.up += s - dp[vv];
for (auto v: adj[u]) if (v != p && v != vv) {
hv.up += s - dp[v];
for (auto p: hv) {
hu.add(p.k, p.m + hv.up);
}
}
} else {
HH[u] = u;
}
hu.add(sw[u], s + sqr(sw[u]));
dp[u] = sqr(sw[p]) + hu.query(-2*sw[p]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
RD(n); REP_1(i, n) RDD(sw[i]);
DO(n-1) {
int u, v; RD(u, v);
adj[u].PB(v);
adj[v].PB(u);
}
dfs(1,0);
OT(dp[1]);
}
