Original link: https://www.shuizilong.com/house/archives/spoj-twopaths-two-paths/
Question: Find the maximum value of the product of two disjoint paths.
Analysis: The dfs order maintains diameter has a very nice property. . . That is, you can find the diameter inside the subtree and the diameter outside the subtree. . So we only need to do dfs again, and then multiply the two diameters every time the query comes out. . It’s a pity that O(nlogn) may not be able to pass big data. . .
#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 depth // dd father's depth #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;
xd = max(ld, rd);
x.dd = min(l.dd, r.dd);
x.ld = max(l.ld, r.ld, ld - r.dd);
x.rd = max(l.rd, r.rd, rd - l.dd);
xD = max(lD, rD, l.ld + rd, ld + 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;
}
This article is transferred from: https://www.shuizilong.com/house/archives/spoj-twopaths-two-paths/
This site is only for collection, and the copyright belongs to the original author.