Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
using namespace std; typedef long long ll; const int maxn = 2e5 + 10; const int logn = 18; int parent[maxn][logn]; vector
depth(maxn, 0); int kth_ancestor(int node, int k) { if(depth[node] < k) { return -1; } for(int i = logn; i >= 0; i--) { if(node == -1) { break; } if(k & (1 << i)) { node = parent[node][i]; } } return node; } int main() { int n, q; cin >> n >> q; vector
tree(n + 1, -1); for(int i = 2; i <= n; i++) { cin >> tree[i]; parent[i][0] = tree[i]; } tree[1] = 1; for(int i = 1; i <= n; i++) { if(i != 1) { depth[i] = depth[tree[i]] + 1; } parent[i][0] = tree[i]; for(int j = 1; j <= logn; j++) { parent[i][j] = parent[parent[i][j - 1]][j - 1]; } } while(q--) { int node, k; cin >> node >> k; cout << kth_ancestor(node, k) << endl; } return 0; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)