#include <iostream> #include <vector> #include <queue> using namespace std; void bfs(vector<vector<int> >& data, vector<int>& sumfloor, vector<bool>& rootflag, int rootnum) { queue<int> myq; myq.push(rootnum); while (!myq.empty()){ int sum = 0; int size = myq.size(); //每层数目 while (size > 0) { int nowindex = myq.front(); myq.pop(); //cout << rootflag[nowindex]; if (rootflag[nowindex] == false) { sum += data[nowindex][0]; } if (data[nowindex][1] != -1) { myq.push(data[nowindex][1]); } if (data[nowindex][2] != -1) { myq.push(data[nowindex][2]); } rootflag[nowindex] = true; size--; } sumfloor.push_back(sum); } } bool IsASD(vector<vector<int> >& data, vector<bool>& rootflag) { //找根节点 int rootnum = 0; for (int i = 0; i < rootflag.size();++i) { if (rootflag[i] == true) { rootnum = i; rootflag[i] = false; break; } } /* for (auto num : rootflag) { cout << num << " "; }*/ vector<int> sumfloor; bfs(data, sumfloor, rootflag, rootnum); int i = 0; while (i < sumfloor.size()-1) { if (sumfloor[i] > sumfloor[i + 1]) { return false; } ++i; } return true; } int main() { int T; cin >> T; for (int i = 0; i < T; ++i) { int N; //节点数 cin >> N; vector<vector<int> > data(N, vector<int>(3,0)); vector<bool> rootflag(N, true); for (int j = 0; j < N; ++j) { cin >> data[j][0] >> data[j][1] >> data[j][2]; if(data[j][1]!=-1) rootflag[data[j][1]] = false; if (data[j][2] != -1) rootflag[data[j][2]] = false; } /* for (auto num : rootflag) { cout << num << " "; }*/ if (IsASD(data, rootflag)) { cout << "YES" << endl; } else { cout << "NO" << endl; } } system("pause"); return 0; }