题面
链接
C. Kefa and Park
题意
求叶节点数量,叶节点满足,从根节点到叶节点的路径上最长连续1的长度小于m
题解
这道题目主要是实现,当不满足条件时直接返回。
到达叶节点后统计答案,用vector存图的话,无向图时,叶节点的边只有一条,也就是
g
[
i
]
.
s
i
z
e
(
)
=
=
1
g[i].size()==1
g[i].size()==1而不是0
需要特判是一条链的情况,一条链的话根节点的
g
[
i
]
.
s
i
z
e
(
)
=
=
1
g[i].size()==1
g[i].size()==1也成立文章来源:https://www.toymoban.com/news/detail-825824.html
代码
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=1e5+10;
vector<int>g[N];
int a[N],ans,n,m;
void dfs(int u,int fa,int sum,int maxx){
if(maxx>m){
return;
}
//统计答案
if(g[u].size()==1&&max(maxx,sum+a[u])<=m&&u!=1){
// cout<<"----------"<<u<<endl;
ans++;
return;
}
for(auto y:g[u]){
if(y==fa) continue;
if(a[u]==1){
if(a[fa]==1){
dfs(y,u,sum+1,max(maxx,sum+1));
}else{
dfs(y,u,1,max(maxx,1*1ll));
}
}else{
dfs(y,u,0,maxx);
}
}
}
void solve()
{
cin>>n>>m;
rep(i,1,n){
cin>>a[i];
}
rep(i,1,n-1){
int u,v;cin>>v>>u;
g[u].pb(v);
g[v].pb(u);
}
//当前结点、根节点,目前连续猫数。
dfs(1,0,0,0);
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
总结
这道题目主要是dfs的实现,树的遍历,以及在遍历过程中维护相关信息。同时需要考虑一些细节,特殊情况比如树是一条链。文章来源地址https://www.toymoban.com/news/detail-825824.html
到了这里,关于Codeforces Round 303 (Div. 2)C. Kefa and Park(DFS、实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!