Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // (┬┬﹏┬┬)
- #include <bits/stdc++.h>
- using namespace std;
- #define lli long long int
- #define Endl endl;
- #define yy cout << "YES" << endl
- #define nn cout << "NO" << endl
- long long int inf = 1000000007;
- #define all(x) x.begin(), x.end()
- const char nl = '\n';
- void sot(vector<lli>&v) {
- sort(all(v));
- }
- void ipv(vector<lli>&v, lli n) {
- for (lli i = 0; i < n; i++)cin >> v[i];
- }
- void opv(vector<lli>&v, lli n) {
- for (lli i = 0; i < n; i++)cout << v[i] << " ";
- }
- void ipvm(vector<lli>&v, lli n, map<lli, lli>&mp) {
- for (lli i = 0; i < n; i++)mp[v[i]]++;
- }
- void opvm(map<lli, lli>mp) {
- for (auto it : mp)cout << it.first << " " << it.second << " ";
- cout << nl;
- }
- void ips(string s) {
- cin >> s;
- }
- lli gcd(lli a, lli b)
- {
- if (a == 0)
- return b;
- return gcd(b % a, a);
- }
- // Function to return LCM of two numbers
- lli lcm(lli a, lli b)
- {
- return (a / gcd(a, b)) * b;
- }
- bool isPrm(lli n)
- {
- if (n <= 1)
- return false;
- for (lli i = 2; i <= sqrt(n); i++)
- if (n % i == 0)
- return false;
- return true;
- }
- //
- //
- //
- //
- //
- // -----------------------graph-LCA-Binary_lifting------------------------------------------------------------------------------
- const lli N = 3e5 + 10;
- const int Log = 18;
- vector<lli>g[N];
- bool vis[N];
- // vector<vector<lli>>up;
- lli up[N][Log];
- vector<lli>parent(N);
- vector<lli>depth(N);
- // ---------------------list dfs-----------------------------------------------------------------------------
- void dfs(lli v, lli par) {
- vis[v] = 1;
- depth[v] = depth[par] + 1;
- up[v][0] = par;
- // cout << v << " " << par << nl;
- for (int j = 1; j < Log; j++) {
- up[v][j] = up[ up[v][j - 1] ][j - 1];
- }
- for (lli ch : g[v]) {
- if (vis[ch] == 0)
- dfs(ch, v);
- }
- }
- lli lca(lli a, lli b) {
- if (depth[a] < depth[b]) {
- swap(a, b);
- }
- lli k = depth[a] - depth[b];
- for (int i = Log - 1; i >= 0 ; --i)
- {
- if (k & (1 << i)) {
- a = up[a][i];
- }
- }
- if (a == b)return a;
- for (int i = Log - 1; i >= 0 ; --i)
- {
- if (up[a][i] != up[b][i]) {
- a = up[a][i];
- b = up[b][i];
- }
- }
- return up[a][0];
- }
- lli kthAncestor(lli v, lli k) {
- for (int i = Log - 1; i >= 0 ; --i)
- {
- if (k & (1 << i)) {
- v = up[v][i];
- }
- }
- return v;
- }
- void cf()
- {
- lli f = 0, e = 0, o = 0, p, q, r, t;
- lli n;
- cin >> n;
- for (int i = 0; i < n - 1; ++i)
- {
- lli u, v;
- cin >> u >> v;
- g[v].push_back(u);
- g[u].push_back(v);
- }
- cin >> q;
- dfs(1, 1);
- while (q--) {
- lli x, y, e;
- cin >> x >> y >> e;
- p = lca(x, y);
- // cout << p << nl;
- lli dis = depth[x] + depth[y] - 2 * depth[p];
- if (dis > e) {
- lli d1 = depth[x] - depth[p];
- if (e > d1) {
- cout << kthAncestor(y, e - d1) << nl;
- } else {
- cout << kthAncestor(x, e) << nl;
- }
- } else {
- cout << y << nl;
- }
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- lli t = 1;
- // cin >> t;
- while (t--)
- {
- cf();
- }
- }
- //-----------------------------------comments----------------------------------------------------------------------------
- //lb(x)= ele eq or greater then x (first occ)
- //ub(x)= ele greater then x
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement