Simplified description :

Given a tree N A dot tree , Find a chain on the tree so that the product of the length of the chain multiplied by the minimum weight of all the points on the chain is the largest .
The chain length is defined as the number of points on the chain .
 

There are several different approaches :

1.sort+ Union checking set + The diameter of the tree . Edge from big to small to join , And look up the set to maintain the connected block , Record the two endpoints of the diameter of the connected block , Update the diameter when merging connected blocks , And use len*bian[i].w Update answers

   With sorting ,O(nlogn)

2. Point divide and conquer + Tree array . It's disgusting when the point divide and conquer path merges . First of all, scan all the sub trees , Take the path minimum as the subscript , The chain length is put into the tree array as the weight .

  Enumerate subtrees and search again , Subtract the contribution of the current subtree first , When searching again, find the maximum suffix value from the tree array . The idea is to set the minimum value in a path of the current subtree

  O(nlog^2)

3. Point divide and conquer

   Divide the spanning subtree into two stacks ? Don't understand, ...O(nlogn)

   The code is too long , It's better to divide and rule while writing

4. Divide and rule the border

https://blog.csdn.net/litble/article/details/80853633

  In fact, the point of divide and conquer itself can also force all the brothers of the weightlifting tree, and then double hands , So you don't need a tree array , But the complexity is O( Degrees ^2nlogn) Of . Not good

It's easy for the two sons to divide and rule

Three times, then divide and rule , The paths of two subtrees are stored in two arrays , According to the minimum value sort, Then enumerate the double pointers in reverse order . The minimum record value is not less than the maximum depth of the current sub tree , Just do it once on the left and right

It must have passed the virtual point x, So the weight of the imaginary point is x A weight .

The weight of the imaginary edge is 0, Real edge is 1, Two point chain length is depth +1

Code :

Be careful , If the opposite son doesn't choose a point , Then the weight of the current center edge cannot be calculated

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define mk(x,y) make_pair(x,y)
#define fi first
#define se second
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=+;
const int inf=0x3f3f3f3f;
int n;
int tot;
int val[N];
struct node{
int nxt,to;
int w;
}e[*N],bian[*N];
int cnt1=,cnt2;
int hd[N],pre[N];
ll ans;
void add(int x,int y,int z){
e[++cnt1].nxt=hd[x];
e[cnt1].to=y;
e[cnt1].w=z;
hd[x]=cnt1;
}
void add_c(int x,int y){
bian[++cnt2].nxt=pre[x];
bian[cnt2].to=y;
pre[x]=cnt2;
}
void rebuild(int x,int fa){
int ff=;
for(reg i=pre[x];i;i=bian[i].nxt){
int y=bian[i].to;
if(y==fa) continue;
if(!ff){
add(x,y,);
add(y,x,);
ff=x;
}else{
int tmp=++tot;
val[tmp]=val[x];
add(ff,tmp,);add(tmp,ff,);
add(tmp,y,);add(y,tmp,);
ff=tmp;
}
rebuild(y,x);
}
} pair<int,int>ls[N],rs[N];
int lsc,rsc;
bool cmp(pair<int,int>A,pair<int,int>B){
if(A.fi==B.fi) return A.se<B.se;
return A.fi<B.fi;
}
int totsz;
int rt1,rt2,edge;
bool vis[*N];
int sz[N],mx;
void dfs1(int x,int fa){
sz[x]=;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
if(vis[i]) continue;
dfs1(y,x);
int now=max(sz[y],totsz-sz[y]);
if(now<mx) {
mx=now;rt1=x;rt2=y;edge=i;
}
sz[x]+=sz[y];
}
}
void dfs2(int x,int fa,int mi,int dep,int typ){
if(typ==){
ls[++lsc]=mk(mi,dep);
}else{
rs[++rsc]=mk(mi,dep);
}
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa||vis[i]) continue;
dfs2(y,x,min(mi,val[y]),dep+e[i].w,typ);
}
}
void divi(int x,int from ){
//cout<<" divi "<<x<<" "<<totsz<<" from "<<from<<endl;
if(totsz==) return; rt1=rt2=edge=;
mx=inf;
dfs1(x,);
//cout<<" rt1 "<<rt1<<" rt2 "<<rt2<<" sz "<<sz[rt1]<<" "<<sz[rt2]<<endl;
vis[edge]=vis[edge^]=;
lsc=rsc=;
dfs2(rt1,,val[rt1],,);
dfs2(rt2,,val[rt2],,);
sort(ls+,ls+lsc+,cmp);
sort(rs+,rs+rsc+,cmp);
int mxdep=;
int ptr=rsc;
for(reg i=lsc;i>=;--i){
while(ptr&&rs[ptr].fi>=ls[i].fi){
mxdep=max(mxdep,rs[ptr].se);--ptr;
}
ans=max(ans,(ll)((ll)mxdep+e[edge].w+ls[i].se+)*ls[i].fi);
}
mxdep=;ptr=lsc;
for(reg i=rsc;i>=;--i){
while(ptr&&ls[ptr].fi>=rs[i].fi){
mxdep=max(mxdep,ls[ptr].se);--ptr;
}
ans=max(ans,(ll)((ll)mxdep+e[edge].w+rs[i].se+)*rs[i].fi);
}
int szrt1=totsz-sz[rt2];
int szrt2=sz[rt2];
int tmprt1=rt1,tmprt2=rt2;
totsz=szrt1;
divi(tmprt1,x);
totsz=szrt2;
divi(tmprt2,x);
}
int main(){
rd(n);
for(reg i=;i<=n;++i) rd(val[i]),ans=max(ans,(ll)val[i]);
int x,y;
for(reg i=;i<n;++i){
rd(x);rd(y);
add_c(x,y);add_c(y,x);
}
tot=n;
rebuild(,);
totsz=tot;
//cout<<" tot "<<tot<<endl;
divi(,);
printf("%lld",ans);
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/25 9:29:02
*/

bzoj2870 The longest road tree—— More articles on Bian Fenzhi

  1. 【BZOJ2870】 The longest road tree Point divide and conquer + Tree array

    [BZOJ2870] The longest road tree Description H It's a big city , Yes N A road junction ( from 1 To N Number ), There is... Between the intersections N-1 edge , So that any two intersections can reach each other , The length of these roads is the same for us . There's a lot of traffic at every intersection ...

  2. BZOJ2870— The longest road tree

    The longest road tree Description H It's a big city , Yes N A road junction ( from 1 To N Number ), There is... Between the intersections N-1 edge , So that any two intersections can reach each other , The length of these roads is the same for us . There's a lot of traffic at every intersection , So every intersection i all ...

  3. [BZOJ2870] The longest road tree: Point divide and conquer

    Algorithm one : Point divide and conquer + Line segment tree analysis It's a line tree , But actually, to write a tree array card . Code #include <bits/stdc++.h> #define rin(i,a,b) for(register ...

  4. BZOJ2870: The longest road tree

    Answer key : The method of sub tree partition can be used here :http://blog.csdn.net/iamzky/article/details/41120733 But the yardstick ... Here's another quick and easy way to write . We are still one ...

  5. bzoj 2870 The longest road tree—— Divide and rule the border

    subject :https://www.lydsy.com/JudgeOnline/problem.php?id=2870 On the border divide and rule :https://www.cnblogs.com/Khada-Jhin/p/ ...

  6. BZOJ2870 The longest road tree( Union checking set +LCA)

    The question (n<=50000) Answer key #include<iostream> #include<cstring> #include<cstdio> #include ...

  7. 【BZOJ2870】 The longest road ( Divide and rule the border )

    [BZOJ2870] The longest road ( Divide and rule the border ) Topic BZOJ Authority questions Description H It's a big city , Yes N A road junction ( from 1 To N Number ), There is... Between the intersections N-1 edge , So that any two intersections can reach each other , The length of these roads is the same for us ...

  8. 【bzoj2870】 The longest road tree The diameter of the tree + Union checking set

    Title Description Given a tree N A dot tree , Find a chain on the tree so that the product of the length of the chain multiplied by the minimum weight of all the points on the chain is the largest . The chain length is defined as the number of points on the chain . Input first line N The second line N Each number represents 1~N Right to the point of v[i] Next N-1 Every line ...

  9. BZOJ2870 The longest road

    The question : Given tree , A little bit of power . Find a path so that the minimum point weight * The total number of points is the largest . Just output the maximum value .5w. Explain : Tree path problem , Point divide and conquer . When considering merging two subtrees , The answer is in the form of val1 * (d1 + d2), When 1 New insertion ...

Random recommendation

  1. 【 Selfless sharing :ASP.NET CORE Project practice ( Chapter vii. )】 File operations FileHelper

    indexes [ Selfless sharing :ASP.NET CORE Project practice ] indexes brief introduction In programming , We have many cases , Will use the operation of the file , stay Previous series in , We have many examples of basic file operations , stay Core There are some changes in , Lord ...

  2. C# PInvoke(DllImport Use ) Advanced tutorial ( One ) turn

    We used to be familiar with WindowsAPI,  We used to spend a lot of time writing code , Are we going to give up easily   But now Microsoft has put downward compatibility in a very important position .C# It's common for programmers to use existing code as part of their own programs ...

  3. Android(java) Learning notes 121:android.intent.action.MAIN And android.intent.category.LAUNCHER understand

    Let's take a look at the Internet : android.intent.action.MAIN Decide which application starts first Activity android.intent.category.LAUNCHER Determines whether the application displays ...

  4. 【QT relevant 】Qt Widgets Module

    Qt Widgets Module: Provides some columns UI Elements . Use : // The header file contains #include <QtWidgets> // Link mode , stay .pro Add lines to the file : QT += widge ...

  5. Pycharm Installation and problems encountered

    Imagine self-study while it's cold python Language , Recommended eclipse+pydev But because java Programming uses eclipse, I don't really want one IDE For multi language development ( Individual be fond of ), So I downloaded it Pycharm, Between the installation also encountered ...

  6. JS Medium this Point to the problem

    I found that in the right JS I have a lot of friends in my study this There are still some misunderstandings about the direction of the problem, or just a general understanding of it , But when it comes to complicated situations, it's because this Point to the problem and cause all kinds of bug. I've learned before c Or is it Java Maybe this is ...

  7. onmouseover event

    According to the teaching video, I wrote a onmouseover event : <!DOCTYPE html> <html> <head> <meta charset="UTF-8 ...

  8. sqlserver Of over Open the window function ( Used with ranking or aggregation functions )

    First initialize the table and data create table t_student(   Id INT,   Name varchar(),   Score int,   ClassId INT ); insert i ...

  9. Java The foundation is strengthened ( 3、 ... and )Thread in start() and run() The difference between

    Thread in start() and run() The difference between start() : Its function is to start a new thread , The new thread will execute the corresponding run() Method .start() Can't be called repeatedly .run()   : run() It's just like the ordinary one ...

  10. [Medium translate ]RESTful API Authoritative design guide - Design better API

    This is the authorized translation . If you want to see the original text, please stamp the link :https://hackernoon.com/restful-api-design-step-by-step-guide-2f2c9f9fcdbf For our ...