【DSY】Migration 题解

DSY 传送门：Migration

二分 + 贪心 + 双向搜索（思想）。

Solution

1

看到“最大值最小”，考虑二分答案如何做。对于每个状态权值的上限 mid，它的可行性是具有单调性的。直白地，当 mid 大于等于一个临界值，那么一定可以满足最大状态权值小于此上限；反之则一定不满足。

为了方便计算，不妨设定当 V_u=V_v 且 u<v 时，我们当成 V_u<V_v。

2

考虑如何实现函数 check(mid)。即考虑若限定在移动过程中权值的最大值，如何判定能否从 s 变为 t。显然直接考虑从状态 s 跳到状态 t 不好下手（复杂度可能也不允许），所以不妨先分别考虑它们所能到达的权值最小的状态。

不难由此想到贪心：

对于每个棋子初始所在点 i，我们先预处理找到一个节点 j，满足：

• 记 i 到 j 路径上所有节点的权值的最大值为 dis_{i,j}，那么 dis_{i,j}=\min_{k\in son_i}{dis_{i,k}}（son_i 表示当 i 为全树的根时树内的所有节点）。

记 j 为 bst_i。

然后对于每个棋子，设其所在点为 i，只要能在满足“过程中每个状态的权值都小于等于 mid”这个条件的情况下，就一直跳 bst_i，直到不能再跳。这个过程就是贪心，因为每一次从 i 跳到 bst_i，我们都让这个棋子的贡献更小。即当所有初始点都跳到不能再跳时，我们就求出了这个起始状态所能达到的权值最小的状态。最终状态同理。

3

然后我们就能得到起始和终止状态分别能达到的最优状态了。然后本题这个方法的关键点在于：操作具有可逆性。所以我们可以双向搜索。即，当且仅当起始和终止状态所能达到的权值最小的状态相同，它们两个才能互达。

然后此题就结束了。（写代码的时候也没觉得这么复杂啊...

Code

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
const int maxn = 2005;
int n, k, s[maxn], t[maxn], w[maxn];
int dis[maxn], son[maxn], ts[maxn], tt[maxn], bst[maxn];
int l, r = 2000ll * 1e9, ans, u, v;
int cnt, hd[maxn];
struct node{
    int to, nxt;
}e[maxn << 2];

inline int rd(){
    int s = 0, x = 1; char ch = getchar();
    while(ch < '0' or ch > '9'){if(ch == '-') x = -1; ch = getchar();}
    while(ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return x * s;
}
inline void add(int u, int v){
    e[++cnt] = (node){v, hd[u]}; hd[u] = cnt;
}

inline void dfs(int u, int fa, int rt){
    dis[u] = max(dis[fa], w[u]);
    if(w[u] < w[rt] or (w[u] == w[rt] and u < rt))
        if(dis[son[rt]] > dis[u] or !son[rt]) son[rt] = u;
    for(int i = hd[u]; i; i = e[i].nxt){
        int v = e[i].to; if(v == fa) continue;
        dfs(v, u, rt);
    }
}

inline void pre(int x){
    memset(dis, 0, sizeof dis);
    dfs(x, 0, x), bst[x] = dis[son[x]];
}

inline bool chck(int v){
    rep(i, 1, k) ts[i] = s[i], tt[i] = t[i];
    int ss, st; ss = st = 0;
    rep(i, 1, k) ss += w[s[i]], st += w[t[i]];
    if(max(ss, st) > v) return 0;
    int flg = 1;
    while(flg){
        flg = 0;
        rep(i, 1, k) if(son[ts[i]] and ss - w[ts[i]] + bst[ts[i]] <= v)
            ss += - w[ts[i]] + w[son[ts[i]]], ts[i] = son[ts[i]], flg = 1;
        rep(i, 1, k) if(son[tt[i]] and st - w[tt[i]] + bst[tt[i]] <= v)
            st += - w[tt[i]] + w[son[tt[i]]], tt[i] = son[tt[i]], flg = 1;
    }
    rep(i, 1, k) if(ts[i] != tt[i]) return 0;
    return 1;
}

signed main(){
    n = rd();
    rep(i, 1, n) w[i] = rd();
    rep(i, 2, n)
        u = rd(), v = rd(), add(u, v), add(v, u);
    k = rd();
    rep(i, 1, k) s[i] = rd(), t[i] = rd();
    rep(i, 1, n) pre(i);
    while(l <= r){
        int mid = l + r >> 1;
        if(chck(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    } printf("%lld\n", ans);
    return 0;
}