Thứ Năm, 5 tháng 11, 2020

Dùng DFS để duyệt cây và bài toán đếm m con mèo liên tiếp

 Đề bài: $\href{http://codeforces.com/contest/580/problem/C}{Đây}$

Tóm tắt: Cho một cái cây, tại mỗi nút có con mèo hoặc không ?

Hỏi có bao nhiêu cách đi từ gốc đến lá , mà trên đường đi không được đi qua quá m con mèo liên tiếp

Lời giải: 

+ Sử dụng DFS:

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define maxn 100005
  5. vector<ll> adj[maxn];
  6. ll c[maxn];
  7. ll res=0;
  8. ll n,m;
  9. void dfs(ll s, ll parent, ll cats){
  10. if(cats>m) return ;
  11. int ok=1;
  12. for(ll i=0;i<adj[s].size();i++){
  13. if(adj[s][i]!=parent){
  14. ok=0;
  15. dfs(adj[s][i],s,cats*c[adj[s][i]]+c[adj[s][i]]);
  16. }
  17. }
  18. res+=ok;
  19. }
  20. int main(){
  21.  
  22. cin>>n>>m;
  23. ll i;
  24. for(i=0;i<n;i++) cin>>c[i];
  25. for(i=0;i<n;i++){
  26. ll u,v;
  27. cin>>u>>v;
  28. u--;v--;
  29. adj[u].push_back(v);
  30. adj[v].push_back(u);
  31. }
  32. dfs(0,-1,c[0]);
  33. cout<<res;
  34. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...