题目
点这里看题目。
BZOJ 上是权限题目。
分析
这道题可以用点分治，但是我就是喜欢边分治 QAQ 。
分治过程中，我们考虑经过分治边的路径的最大痛苦值。一条经过分治边的路径会被分治边划分成两段（不包括分治边），我们只需要在它的最小值的那一段将它计入答案。
也就是说，对于每一条从分治块中一点到分治边最近端点上的路径，我们只需要计算以它的最小值作为最小值的路径的最优答案（即需要分治边对面的路径长度最长），这样就不会记重。更重要的是，写着不麻烦。
具体实现的时候，由于分治边只会将分治块划分成两块，所以排序后 two-pointers 扫描计算答案。
代码·
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
struct edge
{
int to, nxt, w;
}Graph[MAXN << 1];
struct node
{
int mn, len;
node() { mn = len = 0; }
node( const int M, const int L ) { mn = M, len = L; }
bool operator < ( const node & b ) const { return mn > b.mn; }
}t[2][MAXN];
vector<int> G[MAXN];
int mx[MAXN];
int head[MAXN], score[MAXN], siz[MAXN];
LL ans;
int N, tot, l[2], cnt = 1;
bool vis[MAXN];
void addEdge( const int from, const int to, const int W )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from], Graph[cnt].w = W;
head[from] = cnt;
}
void addE( const int from, const int to, const int W ) { addEdge( from, to, W ), addEdge( to, from, W ); }
void rebuild( const int u, const int fa )
{
int cur, lst = 0;
for( int i = 0, v ; i < G[u].size() ; i ++ )
if( ( v = G[u][i] ) ^ fa )
{
if( ! lst ) addE( lst = u, v, 1 );
else score[cur = ++ tot] = score[u], addE( lst, cur, 0 ), addE( cur, v, 1 ), lst = cur;
rebuild( v, u );
}
}
int getCen( const int u, const int fa, const int all )
{
int ret = 0, tmp; siz[u] = 1;
for( int i = head[u], v, id ; i ; i = Graph[i].nxt )
if( ( v = Graph[i].to ) ^ fa && ! vis[id = ( i >> 1 )] )
{
tmp = getCen( v, u, all );
siz[u] += siz[v];
mx[id] = MAX( siz[v], all - siz[v] );
if( mx[id] < mx[ret] ) ret = id;
if( mx[tmp] < mx[ret] ) ret = tmp;
}
return ret;
}
void DFS( const int u, const int fa, const int d, const int val, const int side )
{
t[side][++ l[side]] = node( val, d );
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( ( v = Graph[i].to ) ^ fa && ! vis[i >> 1] )
DFS( v, u, d + Graph[i].w, MIN( val, score[v] ), side );
}
void divide( const int x, const int all )
{
if( all == 1 ) return ;
int cur = getCen( x, 0, all );
int fr = Graph[cur << 1].to, to = Graph[cur << 1 | 1].to, w = Graph[cur << 1].w;
vis[cur] = true;
l[0] = l[1] = 0;
DFS( fr, 0, 0, score[fr], 0 );
DFS( to, 0, 0, score[to], 1 );
sort( t[0] + 1, t[0] + 1 + l[0] ), sort( t[1] + 1, t[1] + 1 + l[1] );
int mxl = -INF;
for( int i = 1, p = 1 ; i <= l[0] ; i ++ )
{
for( ; p <= l[1] && t[1][p].mn >= t[0][i].mn ; p ++ ) mxl = MAX( mxl, t[1][p].len );
ans = MAX( ans, 1ll * t[0][i].mn * ( t[0][i].len + mxl + w + 1 ) );
ans = MAX( ans, 1ll * t[0][i].mn * ( t[0][i].len + 1 ) );
}
mxl = -INF;
for( int i = 1, p = 1 ; i <= l[1] ; i ++ )
{
for( ; p <= l[0] && t[0][p].mn >= t[1][i].mn ; p ++ ) mxl = MAX( mxl, t[0][p].len );
ans = MAX( ans, 1ll * t[1][i].mn * ( t[1][i].len + mxl + w + 1 ) );
ans = MAX( ans, 1ll * t[1][i].mn * ( t[1][i].len + 1 ) );
}
if( siz[fr] > siz[to] ) siz[fr] = all - siz[to];
else siz[to] = all - siz[fr];
divide( fr, siz[fr] );
divide( to, siz[to] );
}
int main()
{
read( N ); tot = N;
for( int i = 1 ; i <= N ; i ++ ) read( score[i] );
for( int i = 1, a, b ; i < N ; i ++ ) read( a ), read( b ), G[a].push_back( b ), G[b].push_back( a );
rebuild( 1, 0 );
mx[0] = INF, divide( 1, tot );
write( ans ), putchar( '
' );
return 0;
}