1600. 完全二叉树
作者:
logos--
,
2023-03-03 11:14:42
,
所有人可见
,
阅读 172
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 20 + 7;
constexpr int inf = 1E18, mod = 1e9 + 7;
int l[N], r[N], n, max_id, maxk;
bool has_father[N];
inline void dfs(int u, int k) {
if(u == -1) return ;
if(k > maxk) {
maxk = k;
max_id = u;
}
dfs(l[u], 2 * k);
dfs(r[u], 2 * k + 1);
}
inline void Solve() {
memset(l, -1, sizeof l);
memset(r, -1, sizeof r);
cin >> n;
for (int i = 0; i < n; i ++) {
string a, b; cin >> a >> b;
if(a != "-") {
l[i] = stoi(a);
has_father[stoi(a)] = true;
}
if(b != "-") {
r[i] = stoi(b);
has_father[stoi(b)] = true;
}
}
int root = 0;
while(has_father[root]) root ++;
dfs(root, 1);
if(maxk > n) {
cout << "NO" << " " << root << '\n';
}else {
cout << "YES" << " " << max_id << '\n';
}
}
signed main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int T = 1;
for (; T; T --) Solve();
return 0;
}