C++11(clang++ 3.9) 解法, 执行用时: 223ms, 内存消耗: 53728K, 提交时间: 2018-04-05 17:27:52

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>

namespace __board_lovable__ {
	
	using ll = long long;
	const int MAX_N = 2777;
	constexpr ll sqr(ll x) {return x * x;}

	int na, nb;
	int pa[MAX_N], pb[MAX_N], ta[MAX_N], tb[MAX_N];
	int adja[MAX_N], nxta[MAX_N], adjb[MAX_N], nxtb[MAX_N];

	struct Point {
		int x; ll y;
		inline double operator * (const Point& p) const {
			return double(y - p.y) / (x - p.x);
		}
	};

	struct Hull {
		Point q[MAX_N]; 
		double k[MAX_N];
		struct Backup {
			int l, r; Point p; double k;
		}	bak[MAX_N << 1];
		int l, r, top;
		inline void clear() { l = 1; r = 0; top = 0; k[1] = 1.0 / 0.0;}
		inline void add(Point p) {
			bak[++top].l = -1;
			bak[top].r = r;
			if(l > r || k[r] > q[r] * p) ++r;
			else {
				int ll = l, rr = r, mm;
				while(ll < rr) {
					mm = (ll + rr) >> 1;
					(k[mm] <= q[mm] * p) ? rr = mm : ll = mm + 1;
				}
				r = ll;
			}
			bak[top].p = q[r];
			bak[top].k = k[r];
			q[r] = p;
			if(l < r) k[r] = p * q[r - 1]; else k[r] = 1.0 / 0.0;
		}
		inline ll query(int _k) {
			bak[++top].l = l;
			bak[top].r = -1;
			int ll = l, rr = r, mm;
			while(ll < rr) {
				mm = (ll + rr + 1) >> 1;
				k[mm] >= _k ? ll = mm : rr = mm - 1;
			}
			l = ll;
			return q[l].y - (long long) _k * q[l].x;
		}
		inline void restore(int old) {
			for(; top > old; --top) {
				if(bak[top].l == -1) {
					q[r] = bak[top].p;
					k[r] = bak[top].k;
					r = bak[top].r;
				}
				else l = bak[top].l; 
			}
		}
	}	Qf[MAX_N], Qg;
	
	int AA, AA1, BB, BB1, val[MAX_N][MAX_N], *C;
	ll F, G, ans = -(1ll << 60);

	void dfs_b(int p) {
		int old = Qg.top;
		BB = tb[p]; BB1 = tb[pb[p]];
		F = Qf[p].query(-(AA1 << 1)) - sqr(AA1) + C[p];
		if(pb[p] != 1) G = Qg.query(-(BB1 << 1)) - sqr(BB1);
		Qg.add({BB, F - sqr(BB)});
		if(pb[p] != 1) Qf[p].add({AA, G - sqr(AA)});
		if(ans < F) ans = F;
		for(int k = adjb[p]; k; k = nxtb[k]) dfs_b(k);
		Qg.restore(old);

	}
	void dfs_a(int p) {
		AA = ta[p]; AA1 = ta[pa[p]]; C = val[p];
		Qg.clear();
		static int _old[MAX_N][MAX_N]; 
		int *old = _old[p];
		for(int k = 2; k <= nb; ++k) old[k] = Qf[k].top;
		for(int k = adjb[1]; k; k = nxtb[k]) dfs_b(k);
		for(int k = adja[p]; k; k = nxta[k]) dfs_a(k);
		for(int k = 2; k <= nb; ++k) Qf[k].restore(old[k]);
	}

	char buff[1 << 27], *S = buff;
	int next_int() {
		while((*S < '0' || *S > '9') && *S != '-')	++S;
		bool neg = (*S == '-' ? ++S : 0); int ret = 0;
		while('0' <= *S && *S <= '9') ret = ret * 10 + *(S++) - '0';
		return neg ? -ret : ret;
	}

	void __main__() {
		if(!fread(buff, 1, 1 << 27, stdin)) exit(-1);
		na = next_int(); nb = next_int();
		for(int i = 2; i <= na; ++i) ta[i] = next_int();
		for(int i = 2; i <= nb; ++i) tb[i] = next_int();
		for(int i = 2; i <= na; ++i) {pa[i] = next_int(); ta[i] += ta[pa[i]]; nxta[i] = adja[pa[i]]; adja[pa[i]] = i;}
		for(int i = 2; i <= nb; ++i) {pb[i] = next_int(); tb[i] += tb[pb[i]]; nxtb[i] = adjb[pb[i]]; adjb[pb[i]] = i;}
		for(int i = 2; i <= na; ++i) for(int j = 2; j <= nb; ++j) val[i][j] = next_int();

		for(int i = 2; i <= nb; ++i) {Qf[i].clear(); Qf[i].add({0, -sqr(tb[pb[i]])});}
		for(int k = adja[1]; k; k = nxta[k]) dfs_a(k);

		std::cout << ans << std::endl;
	}
}

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0); std::cout.tie(0);
	__board_lovable__::__main__();
}