题意：求两条不相交路径的积的最大值。
分析：dfs 序维护直径 有一个非常棒的性质。。。就是可以求子树内的直径和子树外的直径。。所以我们只要再 dfs 一次，然后每次 query 出来两个直径乘一下。。可惜 O(nlogn) 也许过不了大数据。。。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(1e5) + 9;
int L[N], R[N], dep[N], id[N], nn;
VI adj[N]; int n;
struct rec{
int d, dd, ld, rd, D;
void init(LL _d, LL _dd) {
d = _d; dd = 2*_dd;
D = ld = -INF; rd = _d - dd;
}
} T[N*4];
// max d[l] + d[r] - dd[m]
// l < m <= r
// d 深度
// dd 父亲的深度
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
void upd(int x) {
T[x].d = max(T[lx].d, T[rx].d);
T[x].dd = min(T[lx].dd, T[rx].dd);
T[x].ld = max(T[lx].ld, T[rx].ld, T[lx].d - T[rx].dd);
T[x].rd = max(T[lx].rd, T[rx].rd, T[rx].d - T[lx].dd);
T[x].D = max(T[lx].D, T[rx].D, T[lx].ld + T[rx].d, T[lx].d + T[rx].rd);
}
rec upd(rec l, rec r) {
rec x;
x.d = max(l.d, r.d);
x.dd = min(l.dd, r.dd);
x.ld = max(l.ld, r.ld, l.d - r.dd);
x.rd = max(l.rd, r.rd, r.d - l.dd);
x.D = max(l.D, r.D, l.ld + r.d, l.d + r.rd);
return x;
}
void Build(int x, int l, int r) {
if (l == r) {
T[x].init(dep[id[l]], dep[id[l]]-1);
} else {
Build(lc);
Build(rc);
upd(x);
}
}
void dfs(int u = 1, int p = 0) {
id[L[u] = ++nn] = u;
for (auto v: adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
R[u] = nn;
}
rec Query(int x, int l, int r, int a, int b) {
/*if (b < l || r < a) {
rec x; x.init(-INF,INF);
return x;
}*/
if (a <= l && r <= b) {
return T[x];
} else {
if (b < mr) return Query(lc, a, b);
if (ml < a) return Query(rc, a, b);
return upd(Query(lc, a, b), Query(rc, a, b));
}
}
LL z = 0;
void gao(int u = 1, int p = 0) {
for (auto v: adj[u]) if (v != p) {
LL D = Query(1,1,n,L[v],R[v]).D;
checkMax(z, D * upd(Query(1,1,n,1,L[v]-1), Query(1,1,n,R[v]+1,n)).D);
/*cout << L[v] << " " << R[v] << " " << v << " " << Query(1,1,n,L[v],R[v]).D << " " <<
upd(Query(1,1,n,1,L[v]-1), Query(1,1,n,R[v]+1,n)).D
<< " " << z << endl;*/
gao(v, u);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
dep[0] = INF;
DO(RD(n)-1) {
int x, y; RD(x, y);
adj[x].PB(y);
adj[y].PB(x);
}
if (n > 3) {
dfs(); Build(1, 1, n); gao();
}
cout << z << endl;
}
没办法，只能换根 dp 了。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(1e5) + 9;
int dn[N], up[N]; // 子树内直径，子树外直径
int d[N][3], e[N]; // 子数内 top3 最长距离，子树外最长距离
VI adj[N]; int n;
void upd(int d[], int v) {
if (v > d[0]) d[2] = d[1], d[1] = d[0], d[0] = v;
else if (v > d[1]) d[2] = d[1], d[1] = v;
else if (v > d[2]) d[2] = v;
}
void dfs1(int u = 1, int p = 0) {
for (auto v: adj[u]) if (v != p) {
dfs1(v, u);
upd(d[u], d[v][0] + 1);
checkMax(dn[u], dn[v]);
}
checkMax(dn[u], d[u][0] + d[u][1]);
}
void dfs2(int u = 1, int p = 0) {
for (auto v: adj[u]) if (v != p) {
checkMax(up[v], up[u]);
checkMax(e[v], e[u] + 1);
int t = d[v][0] + 1;
if (d[u][0] == t) {
checkMax(up[v], d[u][1] + d[u][2]);
checkMax(up[v], d[u][1] + e[u]);
checkMax(e[v], d[u][1] + 1);
}
else {
if (d[u][1] == t) checkMax(up[v], d[u][0] + d[u][2]);
else checkMax(up[v], d[u][0] + d[u][1]);
checkMax(up[v], d[u][0] + e[u]);
checkMax(e[v], d[u][0] + 1);
}
dfs2(v, u);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
DO(RD(n)-1) {
int x, y; RD(x, y);
adj[x].PB(y);
adj[y].PB(x);
}
dfs1(); dfs2();
LL z = 0; FOR_1(i, 2, n) checkMax(z, (LL)dn[i] * up[i]);
cout << z << endl;
}
