https://codeforces.com/contest/1292
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";
}
