fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "dynamite"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. const int mod=1e9+7;
  32. const int maxn=3e5+15;
  33. const ll inf=1e17;
  34.  
  35. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  36. ll ran(ll l, ll r)
  37. {
  38.     return uniform_int_distribution<ll> (l, r)(rng);
  39. }
  40.  
  41. inline void rf(){
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(nullptr); cout.tie(nullptr);
  44.     if(fopen(file".inp","r")){
  45.         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  46.     }
  47. }
  48.  
  49. template<typename T> inline void add(T &x, const T &y)
  50. {
  51.     x+=y;
  52.     if(x>=mod) x-=mod;
  53.     if(x<0) x+=mod;
  54. }
  55.  
  56. template<typename T> inline bool maxi(T &a, T b)
  57. {
  58.     if(a>=b) return 0;
  59.     a=b; return 1;
  60. }
  61.  
  62. template<typename T> inline bool mini(T &a, T b)
  63. {
  64.     if(a<=b) return 0;
  65.     a=b; return 1;
  66. }
  67.  
  68. int n, m, val, cnt=0;
  69. int l[maxn], kc[maxn];
  70. bool spe[maxn];
  71. vi g[maxn];
  72.  
  73. void dfs(int u, int par)
  74. {
  75.     if(spe[u]) l[u]=0;
  76.     for(auto v:g[u]) if(v!=par)
  77.     {
  78.         dfs(v, u);
  79.         if(l[v]>-1 && l[v]+1>kc[u]) maxi(l[u], l[v]+1);
  80.         if(l[u]+1<=kc[v]) l[u]=-2, maxi(kc[u], kc[v]-1);
  81.     }
  82.     if(l[u]==val) ++cnt, l[u]=-2, kc[u]=val;
  83. }
  84.  
  85. bool check()
  86. {
  87.     ff(i, 1, n) l[i]=-1, kc[i]=-1e9;
  88.     dfs(1, 0);
  89.     if(l[1]>-1) ++cnt;
  90.     return cnt<=m;
  91. }
  92.  
  93. signed main()
  94. {
  95.     rf();
  96.     cin>>n>>m;
  97.     ff(i, 1, n) cin>>spe[i];
  98.     ff(i, 1, n-1)
  99.     {
  100.         int u, v; cin>>u>>v;
  101.         g[u].pb(v); g[v].pb(u);
  102.     }
  103.     int l=0, r=n/m+1, ans=-1;
  104.     while(l<=r)
  105.     {
  106.         int mid=(l+r)>>1;
  107.         val=mid; cnt=0;
  108.         if(check()) ans=mid, r=mid-1;
  109.         else l=mid+1;
  110.     }
  111.     cout<<ans;
  112.     re;
  113. }
  114.  
  115.  
Success #stdin #stdout 0.01s 11892KB
comments (?)
stdin
copy 
7 2
1 0 1 1 1 1 0
5 7
1 3
4 5
5 6
2 3
3 4
stdout
copy 
1
https://ideone.com/6FtLo5
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!