1 条题解

  • 0
    @ 2025-11-3 0:09:35

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
    
    bool color[100005];
    int ans, n;
    vector <int> e[100005];
    
    bool dfs(int x, int fa) {
    	bool t = 0;
    	for (int i = 0; i < e[x].size(); i++) {
    		int to = e[x][i];
    		if (to != fa && dfs(to, x)) t = 1; // 永远不要将该写 && 的地方写成 &,因为 && 会短路, & 不会 
    	}
    	if (!color[x] && t) ans++; // 白点的子树里有黑点,而根又是个黑点,所以白点被“两芝士夹一面包”了
    	return (color[x] || t); // 返回这个点和这个点的子树是否有黑点
    }
    
    int main() {
    	cin >> n;
    	for (int i = 1; i <= n; i++) cin >> color[i];
    	for (int i = 1; i < n; i++) {
    		int x, y;
    		cin >> x >> y;
    		e[x].push_back(y); e[y].push_back(x);
    	}
    	int x = -1;
    	for (int i = 1; i <= n; i++)
    		if (color[i]) { // 找到黑色点 
    			x = i; break;
    		}
    	dfs(x, 0);
    	cout << ans;
    }
    
    
    • 1

    信息

    ID
    5628
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者