题解：P13279 「CZOI-R4」生长的树
XHZnewlife · · 题解
蒟蒻的第一篇题解，求过
推一下自己的专栏
首先，我们可以注意到这道题中节点的编号是没有任何用处的。
由于可以任意填编号，对于符合
而我们站在完成时的眼光看过去，可以假设我们每次都填了恰好正确的编号。
第一思路
在赛时的紧张环境下，我们很难一下想到正解，于是我们往往可以凭借我们直观感受找到一个第一思路。
样例给了一个很好的示范（记住这句话。
在样例的引导下我们很快就想到了让
但一次时间内我们可以操作无数次。所以通过样例，我们可以想到:深度足够之后，再将多余部分全部剪掉。
所以，我们的直观想法就诞生了——
正解
然而——直观思路只能拿到
问题出在哪里呢？
我们不妨考虑一个这样的例子：
如果是刚才的思路，我们一定不假思索地回答：“
但答案却是“
我们的思维被限制在哪里了呢？
“深度足够之后，‘再’将多余部分全部剪掉。”
在此例子中，第一次生长后就可以剪去最右边的的节点了，这样只需要一次操作。
样例真是害人不浅
我们再画几个图就可以直观感受到对于一个叶子节点深度齐平的子树来说，这个局部就只需要被修剪一次。
我们能否大胆得出结论：深度不同的叶子节点/子树对答案产生贡献。
是深度决定了时刻数，而在刚才的头脑风暴中我们知道了操作数可以在局部更改时刻数,所以深度差别的个数对操作数有贡献。
所以不同深度产生贡献是一定的，同深度不产生贡献也是一定的。
在此贴出赛时代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
struct tree{
vector<int> chid;
}leaf[500010];
int ans=0;
int cnt=0;
void dfs1(int id,int fid,int deep){
cnt=max(cnt,deep);
for(int i=0;i<leaf[id].chid.size();i++){
if(leaf[id].chid[i]!=fid){
dfs1(leaf[id].chid[i],id,deep+1);
}
}
return ;
}
int dfs2(int id,int fid,int deep){
int j=0,o=k;
vector<int> vec;
int _max=0;
for(int i=0;i<leaf[id].chid.size();i++){
if(leaf[id].chid[i]!=fid){
vec.push_back(dfs2(leaf[id].chid[i],id,deep+1));
_max=max(_max,vec[vec.size()-1]);
++j;
}
}
if(j==0)return deep;
for(int i=0;i<vec.size();i++)
if(vec[i]==_max)o--;
ans+=o;
return _max;
}
signed main(){
cin>>n>>k;
if(k==1){
cout<<n-1<<" "<<0;
return 0;
}
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
leaf[u].chid.push_back(v);
leaf[v].chid.push_back(u);
}
dfs1(1,0,1);
dfs2(1,0,1);
cout<<cnt-1<<" "<<ans;
return 0;
}观察到赛时