D. Reset K Edges（dfs/bfs/二分/贪心）

题目 参考

题意

给定一个根为1的一棵树，节点为1到n。现可以执行以下操作

• 选择一条边(u,v)
• 删除边(u,v)
• 建立新边(1,v)

最多可以执行上述操作k次，问最多可以将树砍到多高。树的高度定义为其最深的叶子节点。根节点的深度为0。

思路

二分高度，计算高度为d时，最少需要操作多少次。 对于高度为d，从深度高的叶子节点开始遍历，如果当前节点深度大于d，则用贪心策略，将该节点的第d代祖先的边砍掉，接到根节点上。

如何遍历深度高的叶子节点遍历，用bfs预处理，储存它们的遍历顺序。 如何记录节点的第d代祖先，用dfs预处理。

详见代码

代码

#include 
using namespace std;
#define ll long long
#define pcc pair
#define inf 0x3f3f3f3f
const int maxn = 200010;

int n, k, p;
vector g;
vector st;
int pt[maxn], h[maxn];
vector ord;
bool vis[maxn];
void dfs(int u, int d) {
	st.push_back(u);
	if (st.size() >= d) {
		pt[u] = st[st.size()-d];
	}
	for (auto v: g[u]) {
		dfs(v, d);
	}
	st.pop_back();
}
void dfs2(int u) {
	vis[u] = 1;
	for (auto v: g[u]) {
		if (!vis[v]) {
			dfs2(v);
		}
	}
}
int cal(int d) {
	// 1. cal the ancestor with distance d.
	st.clear();
	memset(pt, -1, sizeof(pt));
	dfs(0, d);
	
	// 2. calculate the depth of every node,
	// and bfs order.
	ord.clear();
	queue q;
	h[0] = 0;
	q.push(0);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		ord.push_back(u);
		for (auto v: g[u]) {
			q.push(v);
			h[v] = h[u] + 1;
		}
	}
	reverse(ord.begin(), ord.end());
	
	// 3. calculate the minist number to keep 
	// the tree hight