https://codeforces.com/contest/1739/problem/D 이 문제 인데..


우선 파라메트릭 인건 찾았고, 되는지 안되는지 판단할 때, 나는 dfs를 써서, 


  1. int d[200001];
  2. int c;
  3. void dfs(int cur, int par) {
  4. d[cur] = 1;
  5. for (int next : v[cur]) {
  6. dfs(next, cur);
  7. d[cur] = max(d[cur], d[next] + 1);
  8. }
  9. if (d[cur] == c && par > 1) {
  10. tmp++, d[cur] = 0;
  11. }
  12. }


이런식으로, 구현을 했는데 고수들 코딩봤더니


  1. bool check(int w){
  2. int ans=0;
  3. for(int i=n;i>=2;i--) d[i]=1;
  4. for(int i=n;i>=2;i--){
  5. if(d[i]==w&&fa[i]!=1) ans++;
  6. else d[fa[i]]=max(d[fa[i]],d[i]+1);
  7. }
  8. return ans<=k;
  9. }


이런식으로 for문 한번으로 확인하더라고


내방식은 dfs 쫙 돌린다음 리프노트부터 보는 거니까 그러려니 하는데 저렇게 for문 한번만 돌리는 거로도 확인이 가능함..??


뭔가 막 중간에 꼬여서 안될 거 같은데 도대체 왜 되는지 이유를 못찾겠음 ㅠㅠ