| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1325321 | Ludissey | Burza (COCI16_burza) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const int LOG=61;
int n,k;
vector<vector<int>> dep_list;
vector<int> dep_ord;
vector<int> dep;
vector<vector<int>> neigh;
vector<vector<int>> child;
unordered_map<int,int> memo;
bool dfs(int x, int p, int d){
if(d==k) {
dep[x]=d;
dep_ord[x]=sz(dep_list[d]);
dep_list[d].push_back(x);
return true;
}
bool b=false;
for (auto u : neigh[x])
{
if(u==p) continue;
if(dfs(u,x,d+1)) {
child[x].push_back(u);
b=true;
}
}
if(b){
dep[x]=d;
dep_ord[x]=sz(dep_list[d]);
dep_list[d].push_back(x);
return true;
}
return false;
}
bool dp(int d, int mask){
if(d==k) return true;
if(mask==0) return true;
if(memo[mask+(d<<(LOG))]==1) return false;
int nmask=0;
for (int i = 0; i < min(LOG,sz(dep_list[d])); i++){
if(!(mask&(1LL<<i))) continue;
for (auto u : child[dep_list[d][i]]){
if(dep_ord[u]>=LOG) return (memo[mask+(d<<(LOG+1))]=false);
nmask+=(1LL<<dep_ord[u]);
}
}
for (int j = 0; j < LOG; j++)
{
if(!(nmask&(1LL<<j))||__builtin_popcount(nmask)-1>=(k-d)) continue;
if(dp(d+1,nmask^(1LL<<j))){
return (memo[mask+(d<<(LOG+1))]=true);
}
}
return (memo[mask+(d<<(LOG+1))]=false);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
child.resize(n);
neigh.resize(n);
dep.resize(n);
dep_ord.resize(n,-1);
dep_list.resize(k+1);
for (int i = 0; i < n-1; i++)
{
int a, b; cin >> a >> b; a--; b--;
neigh[a].push_back(b);
neigh[b].push_back(a);
}
dfs(0,-1,0);
int mask=1;
if(dp(0,mask)){
cout << "DA" << "\n";
}else{
cout << "NE" << "\n";
}
return 0;
}