【NOIP2018模拟賽2018.10.22】咖啡供應

題目

題解

–是貪心呢

先bfs一遍

從深度最深的節點開始處理

盡量向上走最遠

但是這道題卡的很死，不能直接跑dfs

要用一種标記的方法

如果一個點被兒子中的咖啡館範圍覆寫，賦一個正值，表示還可以向周圍覆寫a距離

如果沒有被覆寫，賦一個負值，表示離他兒子中最遠的沒有覆寫的點的距離為-a

顯然當一個節點的值為-k，就要在這裡建一個咖啡館，并把值賦為k

但是從兒子向父親轉移的時候，如果有正有負，要判斷正的是否可以覆寫負的

而且，如果一個節點的值是從兒子的正值減為0與表示負數的0意義不一樣，要特判

最後再判斷1号節點是否為負就行了

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1e6+5;

int n,k;
int head[MAXN],next[MAXN*2],to[MAXN*2],cnt;
int bfn[MAXN],tot;
int f[MAXN],b[MAXN];
int v[MAXN];
bool a[MAXN];
int ans;

void add(int u,int v){
	cnt++;
	next[cnt]=head[u];
	to[cnt]=v;
	head[u]=cnt;
}

void bfs(){
	queue<int>q;
	q.push(1);
	bfn[1]=++tot;
	b[tot]=1;
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=next[i]){
			int y=to[i];
			if(bfn[y])
				continue;
			bfn[y]=++tot;
			b[tot]=y;
			f[y]=x;
			q.push(y);
		}
	}
}

int better(int a,int b){
	if(a<b)
		swap(a,b);
	if(abs(a)>=abs(b))
		return a;
	else
		return b;
}

int main(){
//	freopen("coffee.in","r",stdin);
//	freopen("coffee.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	bfs();
	for(int i=n;i>=1;i--){
		int x=b[i];
		if(v[x]==-k){
			ans++;
			v[x]=k;
		}
		if(v[x]==0&&a[x])
			v[f[x]]=better(v[f[x]],0);
		else{
			v[f[x]]=better(v[f[x]],v[x]-1);
			if(!v[f[x]])
				a[f[x]]=1;
		}
	}
	if(v[1]<0||(!v[1]&&!a[1]))
		ans++;
	cout<<ans;
	return 0;
}