ARC115F Migration

二分答案.

鉴于 $n$ 比较小,先 $\mathcal{O}(n^2)$ Preprocess to figure out where each point optimally jumps to,Make the path maximum value as small as possible,It is guaranteed that it cannot jump to the origin, the weight is less than or equal to the root, and the number is as small as possible.

考虑二分答案 $lim$,Each jumps the optimal point from the start node and the end node respectively,Skip to weights and over $lim$ 为止,Finally, determine whether the corresponding two points are equal,单次时间复杂度 $\mathcal{O}(kn)$.

时间复杂度 $\mathcal{O}(n^2\log V)$.

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ha putchar(' ')
#define he putchar('\n')
typedef long long ll;

inline int read()
{
    
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
    
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * f;
}

inline void write(int x)
{
    
    if(x < 0)
    {
    
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

const int _ = 4010;

int n, k, w[_], a[_], A[_], B[_], val[_], f[_], rt, tot, head[_], to[_ << 1], nxt[_ << 1], s[_], t[_];

void add(int u, int v)
{
    
	to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}

void dfs(int u, int fa, int z)
{
    
	z = max(z, w[u]), a[u] = z;
	if(w[u] < w[rt] || (w[u] == w[rt] && u < rt))
		if(!f[rt] || a[u] < a[f[rt]]) f[rt] = u;
	for(int i = head[u]; i; i = nxt[i])
		if(to[i] ^ fa) dfs(to[i], u, z);
}

bool check(int x)
{
    
	int s1 = 0, s2 = 0;
	for(int i = 1; i <= k; ++i) A[i] = s[i], B[i] = t[i], s1 += w[A[i]], s2 += w[B[i]];
	if(s1 > x || s2 > x) return 0;
	while (1)
	{
    
		bool flg = 0;
		for(int i = 1; i <= k; ++i)
			if (f[A[i]] && s1 - w[A[i]] + val[A[i]] <= x) s1 = s1 - w[A[i]] + w[f[A[i]]], A[i] = f[A[i]], flg = 1;
		for(int i = 1; i <= k; ++i)
			if (f[B[i]] && s2 - w[B[i]] + val[B[i]] <= x) s2 = s2 - w[B[i]] + w[f[B[i]]], B[i] = f[B[i]], flg = 1;
		if(!flg) break;
	}
	for(int i = 1; i <= k; ++i)
		if (A[i] ^ B[i]) return 0;
	return 1;
}

signed main()
{
    
	n = read();
	for(int i = 1; i <= n; ++i) w[i] = read();
	for(int i = 1, u, v; i < n; ++i)
	{
    
		u = read(), v = read();
		add(u, v), add(v, u);
	}
	k = read();
	for(int i = 1; i <= k; ++i) s[i] = read(), t[i] = read();
	for(int i = 1; i <= n; ++i)
	{
    
		rt = i;
		memset(a, 0, sizeof a);
		dfs(i, i, w[i]);
		val[i] = a[f[i]];
	}
	int l = 0, r = 2e12, mid;
	ll ans = 0;
	while(l <= r)
	{
    
		mid = (l + r) >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	write(ans), he;
	return 0;
}