CF1029E Tree with Small Distances
题目描述
给定一颗有根树（根节点为 111）。要求往树中加入一些边使得从根节点到其他节点的距离至多是 222。 求加入边的最小数量。(边全部都是无向的)
输入格式
第一行一个整数 nnn，表示树中的节点个数。 接下来 n−1n−1n−1 行，每行两个整数 x,yx,yx,y，表示 x,yx,yx,y 之间有一条连边。
输出格式
一个整数，表示加入边的最小数量。
题解：
看到最优化想DP，没想出来。正解是贪心。
肯定深度深的最不好伺候，先把深度深的搞定了之后，一层一层再逼近根节点这么搞，肯定是更优秀的。
那怎么伺候深度深的呢？
假设现在深度深的点为\(x\)，如果直接连\(x\)，肯定不划算的。我们如果连上他的父亲\(f\)，那么肯定能使得更多的点符合条件。
于是贪心原则就出来了。感性认知是对的。
具体实现就是用堆来维护一个二元组，先处理深度打的节点，每次取出堆顶节点就打一圈标记。就解决了。
代码：
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=2e5+5;
int n,ans;
int tot,head[maxn],nxt[maxn<<1],to[maxn<<1];
int deep[maxn],fa[maxn];
bool v[maxn];
priority_queue<pair<int,int> >q;
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int f)
{
deep[x]=deep[f]+1;
fa[x]=f;
if(deep[x]>2)
q.push(make_pair(deep[x],x));
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)
continue;
dfs(y,x);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
deep[0]=-1;
dfs(1,0);
while(!q.empty())
{
int x=q.top().second;
q.pop();
if(v[x])
continue;
int f=fa[x];
v[f]=1;
for(int i=head[f];i;i=nxt[i])
{
int y=to[i];
v[y]=1;
}
ans++;
}
printf("%d",ans);
return 0;
}