#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
#define eb emplace_back
#define ssz(x) ((signed)((x).size()))
#define For(i, j, k) for (int i = (j); i <= (k); i++)
#define ForDown(i, j, k) for (int i = (j); i >= (k); i--)
namespace {
ll qpow(ll x, ll y, ll mod) {
ll ans = 1;
x %= mod;
while (y) {
if (y & 1)
(ans *= x) %= mod;
(x *= x) %= mod, y >>= 1;
}
return ans;
}
constexpr int MAXN = 5e5 + 5;
int n, q, dep[MAXN], Ans[MAXN], fa[MAXN], dfn[MAXN], seq[20][MAXN], st2[20][MAXN];
basic_string<int> T[MAXN];
set<pii> f[MAXN];
vector<tuple<int, int, int>> segs;
vector<tuple<int, int, int, int>> qry;
namespace All {
int cnt = 0;
void dfs(int x, int pre) {
dep[x] = dep[pre] + 1, fa[x] = pre;
seq[0][dfn[x] = ++cnt] = x;
for (int v : T[x]) if (v != pre)
dfs(v, x);
}
int LCA(int x, int y) {
if (x == y)
return x;
const auto [l, r] = minmax(dfn[x], dfn[y]);
int f = 31 ^ __builtin_clz(r - l), u = seq[f][l + 1], v = seq[f][r - (1 << f) + 1];
return fa[(dep[u] < dep[v]) ? u : v];
}
int LCA2(int l, int r) {
assert(l <= r);
int f = 31 ^ __builtin_clz(r - l + 1), u = st2[f][l], v = st2[f][r - (1 << f) + 1];
return LCA(u, v);
}
void solve() {
dfs(1, 0);
For(i, 1, 19) For(j, 1, n - (1 << i) + 1) {
int u = seq[i - 1][j], v = seq[i - 1][j + (1 << (i - 1))];
seq[i][j] = (dep[u] < dep[v] ? u : v);
}
For(i, 1, n) st2[0][i] = i;
For(i, 1, 19) For(j, 1, n - (1 << i) + 1) {
int u = st2[i - 1][j], v = st2[i - 1][j + (1 << (i - 1))];
st2[i][j] = LCA(u, v);
}
for (auto [l, r, k, id] : qry) {
cout << dep[LCA2(l, r)] << '\n';
}
}
}
void ins(set<pii> &x, int l, int r) {
auto it = x.lower_bound({r + 1, 0});
if (it != x.end() && it->fi == r + 1)
r = it->se, x.erase(it);
it = x.lower_bound({l, 0});
if (it != x.begin() && prev(it)->se == l - 1)
l = prev(it)->fi, x.erase(prev(it));
x.emplace(l, r);
}
set<pii> bit1[MAXN], bit2[MAXN];
int bit3[MAXN];
int get_ans1(int p, int v) {
auto it = bit1[p].lower_bound({v + 1, 0});
if (it == bit1[p].begin())
return 0;
return prev(it)->se;
}
void ins_chkmax1(int p, int x, int y) {
auto it = bit1[p].lower_bound({x + 1, 0});
if (it == bit1[p].begin())
it = bit1[p].emplace(x, y).fi;
else {
--it;
if (it->se >= y)
return;
if (it->fi == x)
bit1[p].erase(it);
it = bit1[p].emplace(x, y).fi;
}
++it;
while (it != bit1[p].end() && it->se <= y)
it = bit1[p].erase(it);
}
void bit_chkmax1(int p, int x, int y) {
for (; p; p -= p & -p){
ins_chkmax1(p, x, y);
}
}
int bit_getans1(int p, int v) {
int ans = 0;
for (; p <= n; p += p & -p) {
ans = max(ans, get_ans1(p, v));
}
return ans;
}
int get_ans2(int p, int v) {
auto it = bit2[p].lower_bound({v, 0});
if (it == bit2[p].end())
return 0;
return it->se;
}
void ins_chkmax2(int p, int x, int y) {
auto it = bit2[p].lower_bound({x, 0});
if (it == bit2[p].end())
it = bit2[p].emplace(x, y).fi;
else {
if (it->se >= y)
return;
if (it->fi == x)
bit2[p].erase(it);
it = bit2[p].emplace(x, y).fi;
}
while (it != bit2[p].begin() && prev(it)->se <= y)
bit2[p].erase(prev(it));
}
void bit_chkmax2(int p, int x, int y) {
for (; p <= n; p += p & -p)
ins_chkmax2(p, x, y);
}
int bit_getans2(int p, int v) {
int ans = 0;
for (; p; p -= p & -p)
ans = max(ans, get_ans2(p, v));
return ans;
}
void bit_chkmax3(int p, int v) {
for (; p; p -= p & -p)
bit3[p] = max(bit3[p], v);
}
int bit_getans3(int p) {
int ans = 0;
for (; p <= n; p += p & -p)
ans = max(ans, bit3[p]);
return ans;
}
void dfs(int x, int pre) {
dep[x] = dep[pre] + 1;
vector<int> cur = {x};
f[x] = {{x, x}};
for (int v : T[x]) if (v != pre) {
dfs(v, x);
if (ssz(f[v]) > ssz(f[x]))
f[v].swap(f[x]);
for (auto seg : f[v])
ins(f[x], seg.fi, seg.se), cur.eb(seg.fi);
f[v].clear();
}
for (int p : cur) {
auto it = f[x].lower_bound({p + 1, 0});
assert(it != f[x].begin()), it--;
segs.eb(it->fi, it->se, dep[x]);
}
}
inline int getK(tuple<int, int, int> x) {
return get<1>(x) - get<0>(x) + 1;
}
inline int getK(tuple<int, int, int, int> x) {
return get<2>(x);
}
void Main() {
freopen("query.in", "r", stdin);
freopen("query.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n;
For(i, 1, n - 1) {
int u, v;
cin >> u >> v, T[u].push_back(v), T[v].push_back(u);
}
bool flg = 1;
cin >> q;
For(i, 1, q) {
int l, r, k;
cin >> l >> r >> k, qry.eb(l, r, k, i);
flg &= k == r - l + 1;
}
if (flg)
return All::solve();
dfs(1, 0);
sort(segs.begin(), segs.end());
segs.erase(unique(segs.begin(), segs.end()), segs.end());
sort(qry.begin(), qry.end(), [&](const auto &x, const auto &y){
return get<2>(x) < get<2>(y);
});
sort(segs.begin(), segs.end(), [&](const auto &x, const auto &y){
return get<1>(x) - get<0>(x) < get<1>(y) - get<0>(y);
});
{
int j = ssz(qry) - 1;
for (int i = ssz(segs) - 1; ~i && ~j; i--) {
while (~j && getK(qry[j]) > getK(segs[i])) {
auto [l, r, k, id] = qry[j];
Ans[id] = max({Ans[id], bit_getans1(l, r - k + 1), bit_getans2(r, l + k - 1)});
j--;
}
bit_chkmax1(get<0>(segs[i]), get<0>(segs[i]), get<2>(segs[i]));
bit_chkmax2(get<1>(segs[i]), get<1>(segs[i]), get<2>(segs[i]));
}
while (~j) {
auto [l, r, k, id] = qry[j];
Ans[id] = max({Ans[id], bit_getans1(l, r - k + 1), bit_getans2(r, l + k - 1)});
j--;
}
}
sort(qry.begin(), qry.end());
sort(segs.begin(), segs.end());
for (int i = 0, j = 0; i < ssz(segs) && j < ssz(qry); i++) {
while (j < ssz(qry) && get<0>(qry[j]) < get<0>(segs[i])) {
auto [l, r, k, id] = qry[j];
Ans[id] = max({Ans[id], bit_getans3(r)});
j++;
}
bit_chkmax3(get<1>(segs[i]), get<2>(segs[i]));
}
For(i, 1, q) cout << Ans[i] << '\n';
}
}
int main() { return Main(), 0; }
ZJ-0056
京公网安备 11011102002149号