Codeforces Round #614 (Div. 1)

A
点を共有するおじゃまマスが存在してはいけません。隣接している箇所の個数のみを保持すればいいです。

B
まずどっかの点に行ってから上or下に順番に取っていくのが最適です。点を全列挙する際にオーバーフロー
に注意しなければならないですが、僕はx > sx + t || y > sy + tでbreakしました。

C
ある辺に0を書き込んでから両端に1,2,3...とpathを延長していくのが最適です。するとコストは、
s(k) = (0を通るpathの本数)+(0,1を通るpathの本数)+...+(0,1,2,...,kを通るpathの本数)とすれば、s(N-1)となります。

ここでdp[u][v]:=uからvのpath上に0~dist(u,v)-1を書き込んだ時のs(dist(u,v)-1)の最大値

とします。path上にあってuと隣接している点をpとすれば、chmin(dp[u][v],dp[p][v]+cost[u][v])で更新できます。
vも同様にやります。ここでcostはuからvのpathを丸々含むpathの本数となるので、これを前計算で求めておきます。
これが結構難しかったです。根付き木でu,vのsubtreeの頂点数を足し引きするみたいな方針でやったんですが、適当にやったら
lca(u,v)=uの時に破滅しました。このときはcost[u][v]=(N-|subtree(p)|)*|subtree(v)|としなければならず、pをいちいち求めていると
3乗になってTLEします。なのでN=3000であることを活かしてまず最初にlca(u,v)=uとなるような頂点のpairについて頂点の親を順番にみていきながら
求め、残りのpairは|subtree(u)|*|subtree(v)|となることを利用して求めました。最初lcaが必要かなと思ったんですが結局いらずにO(N^2)でした。

上記の嘘で1WA、オーバーフローで1WAしました。絶妙にオーバーフローするんだよね…
あと更新の際pを見つけるのにdeg(u)=O(N)かかる場合があるからO(N^3)になりそうな気がするんですが、
あるuを固定するとdeg(u)かかるのがvの数、つまりN個かかるので、N deg(u)となり、uを全て見てもN 2*(N-1)にしかならずO(N^2)です。
これはかなり非直感的なので勉強になりました。

int N;
vi G[MAX_N];
int cost[3010][3010];
int dist[3010][3010];
int par[3010];
ll dp[3010][3010];
int sub[3010];

void pre(int v, int p) {
	sub[v] = 1;
	par[v] = p;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		pre(n, v);
		sub[v] += sub[n];
	}
}

void qre(int root, int v, int p, int c) {
	dist[root][v] = c;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		qre(root, n, v, c + 1);
	}
}

ll loop(int v, int u) {
	if(v == u) return 0;
	else if(v > u) return loop(u, v);
	else if(dp[v][u] != -1) return dp[v][u];
	else {
		ll res = 0;
		int d = dist[v][u];
		rep(i, 0, sz(G[v])) {
			int n = G[v][i];
			if(dist[n][u] < d) {
				MAX(res, loop(n, u) + cost[v][u]);
			}
		}
		rep(i, 0, sz(G[u])) {
			int n = G[u][i];
			if(dist[v][n] < d) {
				MAX(res, loop(v, n) + cost[v][u]);
			}
		}
		return dp[v][u] = res;
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	pre(0, -1);
	rep(i, 0, N) {
		qre(i, i, -1, 0);
	}
	rep(i, 0, N) {
		int at = i;
		while(at != 0) {
			int nat = par[at];
			cost[i][nat] = (N - sub[at]) * sub[i];
			cost[nat][i] = cost[i][nat];
			at = nat;
		}
	}
	rep(i, 0, N) {
		rep(j, 0, N) {
			if(i == j) continue;
			if(!cost[i][j]) {
				cost[i][j] = sub[i] * sub[j];
			}
		}
	}
	memset(dp, -1, sizeof(dp));
	ll res = 0;
	rep(i, 0, N) {
		rep(j, i + 1, N) {
			MAX(res, loop(i, j));
		}
	}
	cout << res << "\n";
}