题目

给定一棵 \(n\) 个结点的树。现在有 \(k\) 个人，每个人最初在 \(s_k\)，最终必须到达 \(t_k\)。

每个结点有一个势能 \(\varphi\)。某一时刻，如果 \(k\) 个人的位置分别为 \(p_1,p_2,\dots,p_k\)，则当前局面的势能为 \(\Phi=\sum_k\varphi_{p_k}\)。

每一个时刻，你可以将某个人从他当前所在结点移动到树上相邻的一个结点上，直到每个人都到达了自己的目标。最小化这个过程中（包括初始和最后的时刻）的 \(\Phi\) 的最大值。

对于 \(100\%\) 的数据，满足 \(1\le n\le 5\times 10^3,0\le k\le 5\times 10^3\)。

分析

认识到一点：这个过程中我们有可能会让某个人 \(k\) 走出从 \(s_k\) 到 \(t_k\) 的最短路。这是因为，我们可能需要让某些人走到 \(\varphi\) 较小的结点上，从而缓冲另一个人路途上可能经过的极大的 \(\varphi\)。

还是不够具象。由于我们需要最小化任意一个时刻的 \(\Phi\)，所以我们必然需要考虑 \(s\rightarrow t\) 上的 \(\max\)（实际上我们也只需要关心 \(\max\)）。从这一点切入，我们借助 Kruskal 重构树（点权、大根）来分析。

Note.

要点之一。因为我们关心的是每个人走过的最大值，所以可以用点权最大的 Kruskal 重构树来表征可以走到的连通块。

\(s\rightarrow t\)，首先需要 \(s\rightarrow \text{LCA}(s,t)\)。因此把问题拆开来，每个人首先爬到 \(\text{LCA}(s,t)\) 及以上。这就只需要向上跳了。

Note.

另一个要点。如果我们始终考虑到 \(s\rightarrow t\) 的限制，那么走起来会处处掣肘，所以最好先弱化一下问题。而根据路径“先上后下”的结构，自然我们应当先考虑前半部分怎么上跳。

向上跳必然会导致答案增大。设 \(\varphi_u^*\) 为 Kruskal 重构树上 \(u\) 子树内点权最小值，那么初始能够达到的最小状态就是 \(\sum_k\varphi^*_{p_k}\)。此时某个人 \(t\) 上跳的结果就是 \(\sum_k\varphi^*_{p_k}+(\varphi_{\texttt{fa}_t}-\varphi^*_t)\)。注意到，我们已经改写成增量的形式，这样便于分离变量。

很显然，在这之后我们肯定是每次选择 \(\varphi_{\texttt{fa}_t}-\varphi^*_t\) 最小的 \(t\) 进行上跳。持续这样进行，我们最终可以得到一个状态，使得每个人都可以单独到达自己的 \(\text{LCA}\)（但不一定可以一起到达）。显然这是一个必须达到的状态。

反过来，怎么构造后半部分？注意到终止状态完全确定，并且过程存在对称性，所以我们可以构造 \(t\rightarrow \text{LCA}(s,t)\) 的一段路径，并且达到类似的状态。

如果可以将两部分接起来，我们就完成了。而这一条是显然的，比如我们可以将正向构造出的状态调整得和反向构造出的终止状态一样。

因此，用一个堆或者 zkw 线段树维护即可。复杂度为 \(O(nk\log n)\)。

代码

#include <cstdio>
#include <algorithm>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

typedef long long LL;

const LL INF = 1e18;
const int MAXN = 5e3 + 5;

template<typename _T>
inline void Read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

template<typename _T>
inline _T Min( const _T &a, const _T &b ) {
    return a < b ? a : b;
}

template<typename _T>
inline _T Max( const _T &a, const _T &b ) {
    return a > b ? a : b;;
}

struct MyGraph {
    struct Edge {
        int to, nxt;
    } Graph[MAXN << 1];

    int head[MAXN], cnt;

    inline Edge operator [] ( const int &idx ) const { return Graph[idx]; }

    inline void AddE( const int &from, const int &to ) {
        AddEdge( from, to ), AddEdge( to, from );
    }

    inline void AddEdge( const int &from, const int &to ) {
        Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
        head[from] = cnt;
    }
};

MyGraph tre, kru;

int fath[MAXN], dep[MAXN], mn[MAXN];

int fr[MAXN], to[MAXN], lca[MAXN];
int val[MAXN], seq[MAXN];

int N, K;

namespace UFS {
    int fa[MAXN];

    inline void MakeSet( const int &n ) {
        rep( i, 1, n ) fa[i] = i;
    }

    int FindSet( const int &u ) {
        return fa[u] == u ? u : ( fa[u] = FindSet( fa[u] ) );
    }
}

namespace Process {
    LL delt[MAXN];
    int mnIdx[MAXN << 2];
    int bas;

    int beg[MAXN], ed[MAXN];
    bool sati[MAXN];

    inline void Upt( const int &x ) {
        mnIdx[x] = delt[mnIdx[x << 1]] <= delt[mnIdx[x << 1 | 1]] ? mnIdx[x << 1] : mnIdx[x << 1 | 1];
    }

    inline void Build( const int &n ) {
        for( bas = 1 ; bas < n ; bas <<= 1 );
        delt[0] = INF;
        rep( i, 1, n ) {
            int x = i + bas - 1, u = beg[i];
            mnIdx[x] = i, delt[i] = fath[u] ? val[fath[u]] - mn[u] : INF;
        }
        rep( i, bas + n, bas << 1 | 1 ) mnIdx[i] = 0;
        per( i, bas - 1, 1 ) Upt( i );
    }

    inline void Modify( const int &i ) {
        int x = i + bas - 1, u = beg[i];
        delt[i] = fath[u] ? val[fath[u]] - mn[u] : INF;
        for( x >>= 1 ; x ; x >>= 1 ) Upt( x );
    }

    LL Solve() {
        int ever = 0;
        LL mnSu = 0, ret = 0;
        rep( i, 1, K ) {
            ever += sati[i] = beg[i] == ed[i];
            mnSu += mn[beg[i]], ret += val[beg[i]];
        }
        Build( K );
        while( ever < K ) {
            int i = mnIdx[1];
            ret = Max( ret, mnSu + delt[i] ), mnSu -= mn[beg[i]];
            if( ( beg[i] = fath[beg[i]] ) == ed[i] )
                sati[i] = true, ever ++;
            mnSu += mn[beg[i]], Modify( i );
        }
        return ret;
    }
}

void Init( const int &u, const int &fa ) {
    dep[u] = dep[fa] + 1, mn[u] = val[u];
    for( int i = kru.head[u], v ; i ; i = kru[i].nxt )
        if( ( v = kru[i].to ) ^ fa )
            Init( v, u ), mn[u] = Min( mn[u], mn[v] );
}

inline int LCA( int u, int v ) {
    while( u ^ v ) {
        if( dep[u] < dep[v] ) std :: swap( u, v );
        u = fath[u];
    }
    return u;
}

int main() {
    Read( N );
    rep( i, 1, N ) Read( val[i] );
    rep( i, 1, N - 1 ) {
        int u, v; Read( u ), Read( v );
        tre.AddE( u, v );
    }
    Read( K );
    rep( i, 1, K ) Read( fr[i] ), Read( to[i] );
    rep( i, 1, N ) seq[i] = i;
    auto Cmp = 
        [] ( const int &a, const int &b ) -> bool {
            return val[a] == val[b] ? a < b : val[a] < val[b];
        };
    std :: sort( seq + 1, seq + 1 + N, Cmp );
    UFS :: MakeSet( N );
    rep( i, 1, N ) {
        int u = seq[i];
        for( int j = tre.head[u], v ; j ; j = tre[j].nxt )
            if( Cmp( v = tre[j].to, u ) ) {
                v = UFS :: FindSet( v );
                fath[v] = u, UFS :: fa[v] = u;
                kru.AddE( u, v );
            }
    }
    Init( seq[N], 0 );
    rep( i, 1, K ) {
        lca[i] = LCA( fr[i], to[i] );
        Process :: beg[i] = fr[i];
        Process :: ed[i] = lca[i];
    }
    LL ans = Process :: Solve();
    rep( i, 1, K ) Process :: beg[i] = to[i];
    Write( Max( ans, Process :: Solve() ) ), putchar( '\n' );
    return 0;
}