## 【日常小测】路径规划

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;
const int M = N << 1;
const int INF = 1e9;

LL vout;

inline void Add_Edge(int u, int v, int c) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

class Divide_and_Conquer{
int rt,rt_sz,blk_sz,tot,sz[N],vis[N];
struct Data{
int mn,id; LL sum;
inline bool operator < (const Data &B) const {
return mn < B.mn;
}
}sta[N];
public:
void solve(int w, int blk) {
GetRoot(w, blk); vis[w=rt] = 1; tot = 0;
if (!vis[to[i]]) {
DFS(to[i], w, to[i], cost[i], cost[i]);
}
}
if (tot) update();
if (!vis[to[i]]) {
if (sz[to[i]] > sz[w]) sz[to[i]] = blk - sz[w];
solve(to[i], sz[to[i]]);
}
}
}
private:
inline void update() {
sort(sta+1, sta+1+tot);
LL mx1=0,mx2=0; int sur1=0,sur2=0;
for (int i=tot;i;i--) {
vout = max(vout, sta[i].mn * sta[i].sum);
if (sur1 && sur1 != sta[i].id) {
vout = max(vout, (mx1 + sta[i].sum) * sta[i].mn);
} else if (sur2 && sur2 != sta[i].id) {
vout = max(vout, (mx2 + sta[i].sum) * sta[i].mn);
}
if (sta[i].sum > mx1) {
if (sur1 == sta[i].id) {
mx1 = sta[i].sum;
} else {
mx2 = mx1; sur2 = sur1;
mx1 = sta[i].sum; sur1 = sta[i].id;
}
} else if (sta[i].sum > mx2) {
if (sur1 != sta[i].id) {
sur2 = sta[i].id;
mx2 = sta[i].sum;
}
}
}
}
inline void GetRoot(int w, int blk) {
rt_sz = INF; blk_sz = blk;
GetRoot1(w, w);
}
void GetRoot1(int w, int f) {
sz[w] = 1; int mx = 1;
if (to[i] != f && !vis[to[i]]) {
GetRoot1(to[i], w);
sz[w] += sz[to[i]];
mx = max(mx, sz[to[i]]);
}
}
mx = max(mx, blk_sz - sz[w]);
if (mx < rt_sz) rt_sz = mx, rt = w;
}
void DFS(int w, int f, int top, int mn, LL sum) {
bool tag = 1;
if (to[i] != f && !vis[to[i]]) {
DFS(to[i], w, top, mn>cost[i]?cost[i]:(tag=0,mn), cost[i] + sum);
}
}
if (!tag) return;
sta[++tot].mn = mn; sta[tot].id = top; sta[tot].sum = sum;
}
}DAC;

int main() {
for (int i=1,u,v;i<n;i++) {
}
DAC.solve(1, n);
printf("%lld\n",vout);
return 0;
}


#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;
const int M = N << 1;

int stp[N],p[N][2],fa[N][20],anc[N];
struct Edge{int u,v,c;}e[N];
LL vout,dep[N],MX[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

void DFS(int w, int f) {
fa[w][0] = f; stp[w] = stp[f] + 1;
if (to[i] != f) {
dep[to[i]] = dep[w] + cost[i];
DFS(to[i], w);
}
}
}

inline void AddEdge(int u, int v, int c, int id) {
static int E = 1; cost[E+1] = cost[E+2] = c;
e[id] = (Edge){u, v, c};
}

inline LL Dis(int u, int v) {
if (stp[v] < stp[u]) swap(u, v); int p1 = u, p2 = v;
for (int i=19;~i;i--) if (stp[fa[v][i]]>=stp[u]) v = fa[v][i];
if (u == v) return dep[p2] - dep[u];
for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return -(dep[fa[u][0]]<<1) + dep[p1] + dep[p2];
}

int find(int x) {return anc[x]==x?x:anc[x]=find(anc[x]);}

inline LL Merge(int u, int v) {
static LL ret, p1, p2; u = find(u); v = find(v);
if (MX[u] > MX[v]) ret = MX[u], p1 = p[u][0], p2 = p[u][1];
else ret = MX[v], p1 = p[v][0], p2 = p[v][1];
for (int i=0;i<=1;i++) {
for (int j=0;j<=1;j++) {
LL cur = Dis(p[u][i], p[v][j]);
if (cur > ret) {
ret = cur;
p1 = p[u][i];
p2 = p[v][j];
}
}
}
anc[u] = v; MX[v] = ret;
p[v][0] = p1; p[v][1] = p2;
return ret;
}

int main() {
for (int i=1,u,v;i<n;i++) {
}
DFS(1, 1);
for (int j=1;j<20;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
sort(e+1, e+N, [](const Edge &A, const Edge &B){return A.c > B.c;});
for (int i=1;i<=n;i++) {
anc[i] = i;
p[i][0] = p[i][1] = i;
}
for (int i=1;i<n;i++) {
LL tmp = Merge(e[i].u, e[i].v);
vout = max(vout, tmp * e[i].c);
}
printf("%lld\n",vout);
return 0;
}