【贪心】Codeforces 958B2 Maximum Control (medium)

题面在这里

很容易想到\(K=2\)时就是求树的直径

其实就是两次DFS,得到的两个最远点的距离就是直径了

其实\(K\gt 2\)也差不多:

每次从未标记的点中找出深度最大的,用于放新的飞船

然后一路向上,标记路径上所有点并更新答案就好了

挺好想的一个贪心……

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005,maxe=200005;
int n,v,ans,num,fa[maxn],dep[maxn],id[maxn],farson[maxn];
int lnk[maxn],son[maxe],nxt[maxe],tot;
bool vis[maxn];
void add(int x,int y){
son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
void dfs(int x){
dep[x]=0;farson[x]=0;
for (int j=lnk[x];j;j=nxt[j])
if (son[j]!=fa[x]){
fa[son[j]]=x,dfs(son[j]);
if (dep[son[j]]+1>dep[x]) dep[x]=dep[son[j]]+1,farson[x]=farson[son[j]];
}
if (dep[x]==0) farson[x]=x;
}
bool cmp(const int &i,const int &j){
return dep[i]>dep[j];
}
int main(){
scanf("%d",&n);
for (int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(1);
v=farson[1];fa[v]=0;dfs(v);
for (int i=1;i<=n;i++) id[i]=i;sort(id+1,id+1+n,cmp);
vis[v]=1;printf("%d",ans=1),num=1;
for (int t=1,i=id[t];t<=n;t++,i=id[t])
if (!vis[i]){
for (int j=farson[i];j!=fa[i];j=fa[j])
vis[j]=1,ans++;
printf(" %d",ans);num++;
}
for (int i=num+1;i<=n;i++) printf(" %d",ans);
return 0;
}