• 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]);
}