萌新刚学OI,求助,本机AC,提交TLE
查看原帖
萌新刚学OI,求助,本机AC,提交TLE
342912
追求_卓越楼主2020/8/25 19:59
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
const int N = 1e6 + 10;
struct Node {
	int next, to;
}edge[N];
int Head[N], tot;
void Add(int x, int y) {
	edge[++tot].to = y;
	edge[tot].next = Head[x];
	Head[x] = tot;
}
struct node {
	int id, dep;
	node(){}
	node(int a, int b) {
		id = a;
		dep = b;
	}
	bool operator < (const node &a) const {
		return a.dep > dep;
	}
};
std::priority_queue<node> q;
int fa[N], depth[N];
void dfs(int u, int pa) {
	fa[u] = pa;
	depth[u] = depth[pa] + 1;
	q.push(node(u, depth[u]));
	for(int i = Head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if(v == pa) continue;
		dfs(v, u);
	}
}
int vis[N];
int Mark(int u, int d, int pa) {
	vis[u] = 1;
	for(int i = Head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if(v == pa) continue;
		if(d) Mark(v, d - 1, u);
	}
}
int main() {
	int n, m, t;
	scanf("%d%d%d", &n, &m, &t);
	for(int i = 1; i < n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		Add(x, y);
		Add(y, x);
	}
	dfs(1, 0);
	int sum = 0;
	while(!q.empty()) {
		node u = q.top();
		q.pop();
		if(vis[u.id]) continue;
		int d = m;
		while(d) {
			u.id = fa[u.id];
			d--;
		}
		Mark(u.id, m, u.id);
		sum++;
	}
	printf("%d\n", sum);
	return 0;
}
2020/8/25 19:59
加载中...