题解：CF1795F Blocking Chips

· · 题解

考虑一条链，一个黑点只能往左右两边，对于一个前缀考虑显然能选左就左否则就只能右，因为选左边不影响右边所有的黑点。

直接贪心不好维护，套一个二分答案转判定性即可。

树的话是一样的，钦定根为 1，然后对一个子树考虑，能在内部解决就解决掉，否则就只能向外求助。维护出每一个点所有需要要救助的链长和可以帮助别的点的链长，在顶点处贪心合并，分类讨论一下，具体见代码。

#include <bits/stdc++.h>
using namespace std;
mt19937 Rand(665431);
#define LL long long
#define endl '\n'

const int N = 5e5 + 10;
const int inf = 1e9;

int n,m;
int vis[N],c[N];
vector <int> g[N];

int dfs (int u,int f){
    vector <int> v1,v2;
    for (auto v : g[u]){
        if (v == f) continue;
        int w = dfs(v,u);
        if (w >= 0) v1.push_back(w);
        if (w < 0) v2.push_back(-w);
    }
    if (vis[u]){
        if (v2.empty()){
            int mx = 0;
            for (auto i : v1) mx = max(mx,i);
            return (mx >= c[u] ? 0 : -c[u]);
        }else{
            return -inf;
        }
    }else{
        if (v2.size() >= 2) return -inf;
        else if (v2.size() == 1){
            int mx = 0;
            for (auto i : v1) mx = max(mx,i);
            return (mx + 1 >= v2[0] ? 0 : 1 - v2[0]);
        }else{
            int mx = 0;
            for (auto i : v1) mx = max(mx,i);
            return mx + 1;
        }
    }
}
bool P (int x){
    for (int i = 1,j = 0 ; i <= n ; i++){
        if (vis[i]) c[i] = x / m + (vis[i] <= x % m);
        else c[i] = 0;
    }
    return (dfs(1,0) >= 0);
}
void solve(){
    cin >> n;
    for (int i = 1 ; i <= n ; i++) g[i].clear(),vis[i] = 0;
    for (int i = 1 ; i < n ; i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> m;
    for (int i = 1 ; i <= m ; i++){
        int x; cin >> x;
        vis[x] = i;
    }
    int L = 1,R = n - m,ans = 0;
    while (L <= R){
        int mid = (L + R) >> 1;
        if (P(mid)) ans = mid,L = mid + 1;
        else R = mid - 1;
    }
    cout << ans << endl;
}
int main(){ 
    #ifndef ONLINE_JUDGE
        freopen("test.in","r",stdin);
        freopen("test.out","w",stdout);
    #endif 
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while (T--) solve();
    return 0;
}