# 【日常小测】路径规划

### 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;
}


## 20 thoughts to “【日常小测】路径规划”

1. My family members all the time say that I am wasting my time here at web,
but I know I am getting experience daily by reading thes fastidious posts.

style is awesome, keep doing what you’re doing!

4. I was suggested this web site by my cousin. I’m not
sure whether this post is written by him as nobody else know such detailed about my difficulty.
You’re amazing! Thanks!

5. Excellent post. Keep posting such kind of info on your site.
Im really impressed by it.
Hey there, You’ve done an excellent job. I will definitely
digg it and individually suggest to my friends. I am sure they will be benefited from
this website.

6. Do you have any video of that? I’d love to find out some additional information.

7. I’m more than happy to discover this website. I want to to
thank you for ones time just for this wonderful read!!
I definitely really liked every bit of it and i also have you saved to
fav to see new stuff on your blog.

8. I all the time emailed this website post page to all my contacts, as if like to
read it after that my friends will too.

9. I all the time emailed this website post page to all my associates, for the reason that if like to
read it afterward my friends will too.

10. Your mode of telling everything in this paragraph is truly
pleasant, every one can easily understand it, Thanks a lot.

11. It’s genuinely very difficult in this full of activity life to listen news on TV, thus I
just use the web for that reason, and take the latest news.

12. This design is incredible! You certainly know how to
start my own blog (well, almost…HaHa!) Excellent job.
I really enjoyed what you had to say, and more than that, how
you presented it. Too cool!

13. I all the time used to study article in news papers but now as
I am a user of internet so from now I am using net for articles, thanks to web.

14. certainly like your website but you need to check the spelling on quite a few of your posts. A number of them are rife with spelling problems and I to find it very bothersome to inform the truth on the other hand I’ll certainly come back again.

15. hello!,I really like your writing very a lot!
percentage we keep in touch extra approximately your post on AOL?
I need a specialist in this house to unravel my
problem. May be that’s you! Looking forward to look you.

16. I love what you guys tend to be up too. This type of clever work
and reporting! Keep up the very good works guys I’ve

17. Magnificent beat ! I wish to apprentice while you amend your
web site, how can i subscribe for a blog web site? The account helped me a acceptable deal.