Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define maxn 100005
- vector<ll> adj[maxn];
- ll c[maxn];
- ll res=0;
- ll n,m;
- void dfs(ll s, ll parent, ll cats){
- if(cats>m) return ;
- int ok=1;
- for(ll i=0;i<adj[s].size();i++){
- if(adj[s][i]!=parent){
- ok=0;
- dfs(adj[s][i],s,cats*c[adj[s][i]]+c[adj[s][i]]);
- }
- }
- res+=ok;
- }
- int main(){
- cin>>n>>m;
- ll i;
- for(i=0;i<n;i++) cin>>c[i];
- for(i=0;i<n;i++){
- ll u,v;
- cin>>u>>v;
- u--;v--;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- dfs(0,-1,c[0]);
- cout<<res;
- }
Không có nhận xét nào:
Đăng nhận xét