【Codeforces 1385F】Removing Leaves | 拓扑排序

tech2025-07-21  5

题目链接:https://codeforces.com/contest/1385/problem/F

题目大意:

给出一棵树,每次可以对一个顶点删除k个节点,问最多可以删除多少次

题目思路:

刚开始读错题了..以为每次可以删除k个叶子节点,想了好久

删除同一个节点的叶子节点就容易许多了

考虑一个节点成为叶子节点的条件:

首先需要度数为1,其次如果不是初始的叶子节点,那么他需要删除多余的叶子节点

用sz_i代表i节点删除了多少个子节点

当且仅当:

in[i] == 1 && sz[i]%m == 0

此时可以入队成为新的叶子节点

所以,整个过程嵌套一个拓扑排序就好了

Code:

/*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(3) #include <bits/stdc++.h> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; const ll INF=1e17; const int maxn =1e6+700; const int mod= 1e9+7; inline bool read(ll &num) {char in;bool IsN=false; in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p; int in[maxn]; vector<int>v[maxn]; int vis[maxn]; vector<int>g; int sz[maxn]; void work(){ g.clear(); queue<int>q; for(int i=1;i<=n;i++) if(in[i]==1) q.push(i); int ans = 0; while(!q.empty()){ int u = q.front();q.pop(); vis[u] = 1; for(int e:v[u]){ if(vis[e]) continue;///deleted in[e]--;sz[e]++; if(sz[e]%m == 0){ ans++; if(in[e] == 1) q.push(e); } } } printf("%d\n",ans); } int main(){ int T;scanf("%d",&T); while(T--){ read(n);read(m); for(int i=1;i<=n;i++) in[i] = 0,v[i].clear(),vis[i] = 0,sz[i] = 0; for(int i=1;i<=n-1;i++){ int x,y;scanf("%d%d",&x,&y); v[x].push_back(y);in[y]++; v[y].push_back(x);in[x]++; } work(); } return 0; } /*** ***/

 

最新回复(0)