解题历程：
看到题目要求要用最少的消除次数让所有叶子深度相同，通过观察，那么就只需要将所有深度都尝试一遍就行了，可是我当时没多想就用dfs记录所有节点的深度，单独将所有叶子和该叶子的深度存起来，记录最大的深度，从最大深度尝试到深度0，对于深度小于当前尝试深度的叶子，用dfs的方式将与该叶子直接关联的度数小于等于二的节点删除，删除就用一个数组进行标记删除的节点，利用这个原理写一个删除函数，传递的参数就是目标深度和叶子节点的坐标，返回的就是删除步数，这样每层就遍历一次将遍历的结果相加取最小值就是答案，结果超时了，写这个代码写了一个小时，比赛也只剩几分钟了，寄。然后看了高手的代码，发现我的思路没有问题，就是遍历每个深度的方法有问题，遍历时有太多的重复删除。
正确思路：于是我又想到从小的深度往大的深度遍历，利用一个数组记录当前节点子树总数，当前节点也计入其中，那么就可以采用层序遍历的方式遍历树，要删除的步数就是这层节点所有子树节点的总数，和小于这层的分支的节点数，那么就用一个数组记录该节点子树的最大深度，这个数组用于区分要删掉的低于遍历深度的叶子分支，由于删掉的分支在后面的层数都要删掉，就可以用一个变量记录要删除的分支节点数，每遍历一层就加上记录的次数那么就可以得到等式：所有叶子变成当前深度所以需要的步数=小于当前层数叶子的分支节点数+当前深度的所有节点的子树节点数
代码：
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
vector<vector<int>>a(n+1);
vector<int>b(n+1,1),f(n+1,n),dep(n+1),m(n+1);
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
int t=0;
auto dfs=[&](auto& self,int x,int p)->void
{
m[x]=dep[x];
for(auto y:a[x])
{
if(y==p)continue;
dep[y]=dep[x]+1;//记录深度。dfs往下探时的操作
self(self,y,x);
m[x]=max(m[y],m[x]);//dfs往回缩时的操作
b[x]+=b[y];//记录当前节点及以下的节点总数
}
};
dfs(dfs,1,0);
int l=1;
auto dfss=[&](auto& self,int x)->void//标记需要删除的包含叶子x的分支
{
for(auto y:a[x])
{
if(dep[y]<dep[x])
{
if(m[x]!=m[y])//最大深度不同或已被删除
{
m[x]=0;
break;
}
m[x]=0;
l++;
self(self,y);
}
}
};
queue<int>q;
q.push(1);
int s=0;
while(!q.empty())
{
auto u=q.front();
l=1;
if(a[u].size()==1&&u!=1)//坑点，没有u!=1根节点会被当成叶子节点删除
{
dfss(dfss,u);
s+=l;
}
q.pop();
for(auto i:a[u])
{
if(dep[i]>dep[u])
{
f[dep[u]]+=b[i];
q.push(i);
}
}
if(q.empty()||dep[u]!=dep[q.front()])//坑点，先判断空在进行后面的判断
{
f[dep[u]]+=t;
if(!q.empty())
f[dep[q.front()]]=0;
t+=s;
s=0;
}
}
int ans=*min_element(f.begin(),f.end());//以后不用for循环找最值了
cout<<ans<<endl;
}
int main(void )
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int test=1;
cin>>test;
while(test--)
{
solve();
}
return 0;
}
反思与收获：
-
有思路后开始写代码之前要思考一下有没有重复的步骤，如果有的话就要进行优化，不要有侥幸心理，一旦超时就要浪费大量的时间。
-
以后可以用lambda表达式写函数，这样写的函数可以不用提前声明，其标准格式为
auto function=[&](int a,int b)->void{
cout<<a+b<<endl;
}
int n;
auto dfs[&](auto& self,int a,int b)->void{//void是返回值
//[&]表示函数前面的变量都可以在函数里面使用,比如下面的n
n+=3;
self(self,c,a);//c为当前节点，a为上一节点，a是为了避免重复访问父节点
}
dfs(dfs,1,0);
- 以后可以用min_element函数查找数组的最值
- 以后注意度数为1的根
- 先判断是否为空