牛客编程巅峰赛S1第7场

牛客编程巅峰赛S1第7场

牛客编程巅峰赛S1第7场 - 黄金&钻石 A.牛牛打怪兽

题目链接

题目描述

身为屯里第一剑士的牛牛来到训练场里闯关，由于过于勤奋，牛牛的宝剑的耐久度降到了 2 ，这意味着牛牛最多只能打倒两只怪兽，否则将会被淘汰。

训练场的地图可以看作一棵以 1 为根节点的树，训练场的终点为这棵树的叶子结点，树上的每个结点最多有一只怪兽，结点与结点间的边上没有怪兽。

每一个有怪兽的结点上牛牛都需要打倒怪兽才算安全，并且牛牛一旦选定好打怪路线之后便不能走回头路。

请问牛牛有多少种到达终点且不被淘汰的路径。

输入

第一个参数为 n ， ( 1 ≤ n ≤ 100 , 000 ) n ，(1leq nleq 100,000) n，(1≤n≤100,000)

第二个参数为大小为 n-1n−1 的点对 ( u i , v i ) (u_i, v_i) (ui​,vi​) 的集合，其中 ( u i , v i ) (u_i, v_i) (ui​,vi​) 表示结点 u i u_i ui​ 与结点 v i v_i vi​ 之间有一条边， 1 ≤ u i , v i ≤ n 1leq u_i, v_i leq n 1≤ui​,vi​≤n
第三个参数为大小为 n 的 0/1 序列 f ，若 f i f_i fi​ 为 0 表示 i − 1 i-1 i−1 结点没有怪兽，否则表示 i − 1 i-1 i−1 结点有怪兽。

返回
一个整数，表示牛牛能到达终点且不被淘汰的路径数。

示例1

输入

7,[(7,2),(6,1),(5,2),(1,2),(4,6),(6,3)],[0,0,1,0,1,0,0]

输出

4

吐了，第二次打这种比赛，我以为代码只能写在方法里，看了别人过的代码好像类里是可以定义函数的，这直接导致了我这题不能 DFS，我是用 BFS 的，对每一个叶子结点 (1除外)，如果此时剩的血量大于等于 0 0 0 则答案加 1 1 1，比较恶心的地方是血量和结点序号是差一的，否则你会一直 WA，AC代码如下:

int solve(int n, vector<Point>& Edge, vector<int>& f) {if(n==1||n==2) return 1;//特判int ans=0,vis[100005],hp[100005];memset(vis,0,sizeof(vis));memset(hp,0,sizeof(hp));vector<int>g[100005];for(Point i:Edge){g[i.x].push_back(i.y);g[i.y].push_back(i.x);}queue<int>q;q.push(1);hp[1]=2;while(!q.empty()){int a=q.front();if(g[a].size()==1&&a!=1){if(f[a-1]&&hp[a]>=1) ans++;else if(!f[a-1]&&hp[a]>=0)ans++;}vis[a]=1;q.pop();for(int b:g[a]){if(!vis[b]){q.push(b);if(f[a-1]) hp[b]=hp[a]-1;else hp[b]=hp[a];}}}return ans;
}