哪位dalao能提供一下hack数据或者指出我的方法错在哪里了吗?谢谢!
我的思路是:把所有外围的白色节点全部去掉,最终剩下一棵根节点和叶子节点都是黑色的树,里面余下的白色节点数量就是答案
代码:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int blk[100005],n,ans;
vector<int> G[100005];
queue<int> q;
void bfs()
{
while(!q.empty())
{
int now=q.front();
q.pop();
//cout<<now<<endl;
int i,j;
//erase太麻烦,-1为标记删除
for(i=0;i<G[now].size()&&G[now][i]==(-1);i++){}
if(G[G[now][i]].size()==2&&!blk[G[now][i]])//会不会产生新的叶子结点
{
q.push(G[now][i]);//如果会,就加进队列
}
//在当前节点的父节点的边集里找到当前节点并删除
for(j=0;j<G[G[now][i]].size()&&G[G[now][i]][j]!=(G[now][i]);j++){}
G[G[now][i]][j]=(-1);
ans--;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>blk[i];
if(!blk[i]) ans++;
}
for(int i=1;i<n;i++)
{
int x,y;cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(G[i].size()==1&&!blk[i])
{
q.push(i);
}
}
bfs();
cout<<ans;
return 0;
}