# 【日常小测】路径规划

### 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],fa[N],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] = 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]]<<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], p2 = p[u];
else ret = MX[v], p1 = p[v], p2 = p[v];
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] = p1; p[v] = 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] = p[i] = 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. coconut oil on说道：

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.

2. plenty of fish dating site说道：

3. ps4 games说道：

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

4. ps4 games说道：

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. ps4 games说道：

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. quest bars cheap说道：

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

7. quest bars cheap coupon twitter说道：

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. ps4 games说道：

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. ps4 games说道：

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. quest bars cheap说道：

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

11. quest bars cheap说道：

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. ps4 games说道：

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. coconut oil说道：

Touche. Outstanding arguments. Keep up the great work.

14. coconut oil说道：

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.

15. oprolevorter说道：

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.

16. 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.

17. sling tv说道：

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

18. sling tv说道：

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.
offered bright clear concept

19. sling tv说道：

Greetings from Idaho! I’m bored at work so I decided to browse your website on my iphone during lunch break.
I love the info you present here and can’t wait to take a look when I get home.
I’m surprised at how fast your blog loaded on my phone ..

I’m not even using WIFI, just 3G .. Anyways, awesome site!

20. sling tv说道：

Hurrah! Finally I got a weblog from where I know how to
really get helpful information regarding my study and knowledge.