题解 CF580C 【Kefa and Park】
sukimo
2020-04-09 14:25:16
一道搜索题，思路就是从根节点开始dfs找路径的时候统计。之前被卡过几次，后来找到了错误。对于每个dfs到的节点，维护$3$个参数：
$1$.当前节点编号
$2$.以当前节点结尾的连续点权为$1$的节点个数
$3$.从根节点走到当前节点的路径，最大连续点权为$1$的节点个数
三个信息都比较好维护，其中参数$2$和$3$需要互相更新（见代码，只要理解了上面三个参数的意义，代码非常好理解）。如果在半路参数$3$就大于$m$了，可以直接剪掉。我采用的判断叶节点方法是记下每个点的连边数量，如果只连了一条边且不是根节点（第二个条件很重要！！，因为可以造出两点一边的特殊数据，这时根节点也只连了一条边），就是叶节点。
上代码：
```
#include<bits/stdc++.h>
using namespace std;
const int MX=100005;int m,tot,in[MX],vis[MX],fir[MX],val[MX];struct STR{int next,to;}edge[MX<<1];
void add(int u,int v,int cnt){edge[cnt].to=v;edge[cnt].next=fir[u];fir[u]=cnt;}
void dfs(int x,int now_cnt,int _max){
if(_max>m)return;if(!(in[x]-1)&&x-1){tot++;return;}
vis[x]=1;
for(int i=fir[x];i;i=edge[i].next)
if(!vis[edge[i].to]){
int q=val[edge[i].to]?now_cnt+1:0;dfs(edge[i].to,q,max(_max,q));
}
}
int main(){
int n;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&val[i]);
for(int i=1;i<=n-1;i++){int u,v;scanf("%d%d",&u,&v);add(u,v,i);add(v,u,i+n-1);in[u]++;in[v]++;}
dfs(1,val[1],val[1]);printf("%d",tot);
return 0;
}
```