文章目录

Wannafly挑战赛28 msc的宠物

题意:

给定一棵树，树上每个节点有权值，要求删除最多k条边使得所有联通块的最大值和最小的差最大的最小

分析:

最小化最大值，很明显是二分最大的差值D了
转化一下题目其实就是将树上的节点分成k个联通块，使得所有联通块的最大值和最小的差最大的最小。

状态：

  • f[x] 表示至少删除F[x] 个才能使得x子树差值不超过D
  • g[x][u] 表示至少删除g[x][u] 个才能使得子树最大值为a[u]

状态转移:

设y是x的子节点

  • 如果 a[y] <= a[u] <= a[y]+D,g[x][u] = min(f[y]+1,g[x][u]);（直接断开这条边或者留下这条边）
  • 否则g[x][u] = f[y]+1; （直接断开这条边）
  • f[x] = min(g[x][u]);

参考代码


#include <bits/stdc++.h>
#define Pb push_back
using namespace std;
typedef long long LL;
// const int INF = 0x7FFFFFFF;
const LL     INFF =1e15;
const int maxn = 1000+10;
LL f[maxn],g[maxn][maxn];
LL a[maxn];
LL val[maxn];

std::vector<int> G[maxn];
LL D;
 int n,k;
void dfs(int node,int fa){
  for(int i = 1;i <= n; ++i)
    {
      if(a[node] <= a[i] && a[i] <= a[node]+ D)
         g[node][i] = 0;
      else
         g[node][i] = INFF;
    }

  for(int i = 0;i < (int) G[node].size();++i){
    int v = G[node][i];
    if(v == fa) continue;
    dfs(v,node);
    for(int u = 1;u <= n; ++u){
       if(a[v] <= a[u] && a[u] <= a[v]+D)
        g[node][u]  += min(f[v]+1,g[v][u]);
       else
        g[node][u]  += f[v]+1;
    }
  }
  f[node] = INFF;
  for(int i = 1;i <= n; ++i)
    f[node] = min(f[node],g[node][i]);
}
LL check(LL mid){

  D = mid;
  dfs(1,-1);
  // cout<<D<<" "<<f[1]<<endl;
  // cout<<f[1]<<endl;
  return f[1];
}
int main(void)
{
  
   cin>>n>>k;
   for(int i = 1;i <= n; ++i)
      scanf("%lld",&a[i]);//,val[i] = a[i];
   // sort(val+1,val+n+1);
   for(int i = 1,v,u;i < n; ++i){
     scanf("%d%d",&u,&v);
     G[u].Pb(v);
     G[v].Pb(u);
   }
   LL l = 0,r = 1000000000+2;
   while(r >= l){
       LL mid = (r+l)>>1;
       if(check(mid) <= k)// < 说明差值可以缩小，> 说明差值过小
          r = mid-1;
       else
          l = mid+1;
   }
   cout<<l<<endl;


   return 0;
}