[HNOI2003] 소방서의 설립

제목 링크:https://www.luogu.org/problemnew/show/P2279
해석 부분은 이 사나이의 블로그를 보십시오.https://www.luogu.org/blog/contributation/solution-p2279
이 문제의 코드:

//   dis  ， dis[i]    i           
#include
#include
#include
using namespace std;

const int N=1e3+10, INF=0x3f3f3f3f;
int n, ans, d[N], f[N], seq[N], dis[N];

bool cmp(int a, int b) {
    return d[a]>d[b];
}

int main() {
    memset(dis, INF, sizeof(dis));
    cin >> n;
    seq[1]=1;
    for (int i=2; i<=n; i++) {
        cin >> f[i];
        d[i]=d[f[i]]+1;
        seq[i]=i;
    }
    sort(seq+1, seq+n+1, cmp);            
    for (int i=1; i<=n; i++) {
        int cur=seq[i], last=f[cur], lasts=f[last];//        
        dis[cur]=min(dis[cur], min(dis[last]+1, dis[lasts]+2));//  dis  
        if (dis[cur]>2) {//         
            dis[lasts]=0;//                
            ans++;
            dis[f[lasts]]=min(dis[f[lasts]], 1), dis[f[f[lasts]]]=min(dis[f[f[lasts]]], 2);//  dis  
        }
    }
    cout << ans;
    return 0;
}
//                  ，                   ，        dis  ，                     

ps: 또한 트리의 최대 독립 집합과 최소 덮어쓰기를 구분하십시오. 최소 덮어쓰기는 전체 그림을 최소한의 점으로 덮어쓰는 것을 강조하고 최대 독립 집합은 이 점에 따라 선택하면 하위 노드와 부 노드는 선택할 수 없습니다. 선택하지 않으면 하위 노드와 부 노드는 제목에 따라 선택할 수 없습니다.https://www.luogu.org/problemnew/show/P1352이 문제를 위 소방서와 비교해 더 잘 이해할 수 있다.
사내가 말한 보편성에 관해서는 최소 k로 덮어쓰는 코드를 제시한다.

#include
#include
#include
using namespace std;

const int N=1e3+10, INF=0x3f3f3f3f;
int n, k, ans, cnt, d[N], f[N], ancestor[N], seq[N], dis[N];
// ancestor      k       

bool cmp(int a, int b) {
	return d[a]>d[b];
}

void update(int cur) {
	memset(ancestor, 0, sizeof(ancestor));
	ancestor[0]=cur;
	for (int i=1; i<=k; i++) {
		if (f[ancestor[i-1]]==0) break;
		ancestor[i]=f[ancestor[i-1]];
	}
	return ;
}

int main() {
	memset(dis, INF, sizeof(dis));
	cin >> n;
	seq[1]=1;
	k=2;
	for (int i=2; i<=n; i++) {
		cin >> f[i];
		d[i]=d[f[i]]+1;
		seq[i]=i;
	}
	sort(seq+1, seq+n+1, cmp);
	for (int i=1; i<=n; i++) {
		update(seq[i]);
		for (int j=1; j<=k; j++) {
			if (ancestor[j]==0) break;
			dis[ancestor[0]]=min(dis[ancestor[0]], dis[ancestor[j]]+j);
		}
		if (dis[ancestor[0]]>k) {
			dis[ancestor[k]]=0;
			ans++;
			update(ancestor[k]);
			for (int j=1; j<=k; j++) {
				if (ancestor[j]==0) break;
				dis[ancestor[j]]=min(dis[ancestor[j]], j);
			}
		}
	}
	cout << ans;
	return 0;
}
//   O(nk)