# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1102179 | hiepsimauhong | Untitled (POI11_dyn) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int oo = 1e18;
#define quickly ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define print(a,l,r) for(int OK(l); OK <= r ; ++OK){ if(a[OK] < oo){cout << a[OK] <<' ';} else{cout << "- ";}} cout << '\n';
#define prints(a) for(auto i : a){ cout << i <<' ';} cout << '\n';
#define printz(a,l,r) for(int OK(1) ; OK <= l ; ++OK){for(int KO(1) ; KO <= r ; ++KO){if(a[OK][KO] < oo){cout << a[OK][KO] <<' ';}else{cout << "- ";}}cout << '\n';} cout << '\n';
#define fs first
#define sd second
#define ii pair<int, int>
#define iii pair<int, ii>
#define all(a) a.begin(), a.end()
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
const int lg = 17;
int n, m, cnt(0);
bool bom[N];
int mx_high[N];
vector<int> a[N];
void DFS(int u, int par, int mx){
if(cnt > m){
return;
}
mx_high[u] = 0;
for(int v : g[u]){
if(v == par){
continue;
}
DFS(v, u, mx);
mx_high[u] = max(mx_high[u], mx_high[v] + 1);
}
if(mx_high[u] > mx){
mx_high[u] = 0;
++cnt;
}
}
signed main(){ quickly
cin >> n >> m;
for(int i(1) ; i <= n ; ++i){
cin >> bom[i];
}
for(int i(1) ; i < n ; ++i){
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
int l = 1, r = n;
int ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
cnt = 0;
DFS(1, -1, mid);
if(cnt > m){
l = mid + 1;
}
else{
r = mid - 1;
ans = mid;
}
}
cout << ans;
}