CodeForces1143#C题解

正文

♦时间复杂度：\(\mathcal{O}(n)\)

思维题，不需要建树。

设数组 \(a\) 记录每一个节点是否尊重它的父节点，数组 \(b\) 记录是否有节点尊重它，特别的，叶子节点必然不被尊重。

对于每次的输入数据 \(x,y\)。若 \(y\) 等于 1（即不尊重它的父节点），那 \(a_i \leftarrow 1\)；若 \(y\) 等于 0，那 \(b_a\leftarrow 1\)，最后遍历一遍，如果 \(a_i=1,b_i\ne 1\)，那么代表这个节点既不尊重它的父节点，也没有子节点尊重它，输出。

代码：

#include
using namespace std;
int n;
pair a[(int)1e5+5];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int f,b;
cin>>f>>b;
if(b==0)
a[f==-1?0:f].secOnd=true;
else a[i].first=true;
}
bool flag=true;
for(int i=1;i<=n;i++){
if(a[i].first and !a[i].second){
flag=false;
cout< }
}
if(flag) cout<<-1;
}


洛谷提交记录，华丽结束。

后附

日志

v1.0 on 2022.10.01: 发布