平顶山北京网站建设,动态ppt模板下载免费完整版,疾控网站建设宗旨和目的,营销外贸网站建设文章目录 题面链接题意题解代码总结 题面 链接
C. Kefa and Park
题意
求叶节点数量#xff0c;叶节点满足#xff0c;从根节点到叶节点的路径上最长连续1的长度小于m
题解
这道题目主要是实现#xff0c;当不满足条件时直接返回。 到达叶节点后统计答案#xff0c;用… 文章目录 题面链接题意题解代码总结 题面 链接
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也成立
代码
#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 pairint, int
#define pll pairlong long, long long
#define ll long long
#define db double
#define endl \n
#define x first
#define y second
#define pb push_backusing namespace std;
const int N1e510;
vectorintg[N];
int a[N],ans,n,m;void dfs(int u,int fa,int sum,int maxx){if(maxxm){ return;}//统计答案if(g[u].size()1max(maxx,suma[u])mu!1){
// cout----------uendl;ans;return;}for(auto y:g[u]){if(yfa) continue;if(a[u]1){if(a[fa]1){dfs(y,u,sum1,max(maxx,sum1));}else{dfs(y,u,1,max(maxx,1*1ll));}}else{dfs(y,u,0,maxx);}}
}void solve()
{cinnm;rep(i,1,n){cina[i];}rep(i,1,n-1){int u,v;cinvu;g[u].pb(v);g[v].pb(u);}//当前结点、根节点目前连续猫数。dfs(1,0,0,0);coutansendl;
}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的实现树的遍历以及在遍历过程中维护相关信息。同时需要考虑一些细节特殊情况比如树是一条链。
