比赛 |
2025.1.14 |
评测结果 |
AAAAATTTTTTTTAAATTTTTTTTT |
题目名称 |
树上查询 |
最终得分 |
32 |
用户昵称 |
flyfree |
运行时间 |
59.967 s |
代码语言 |
C++ |
内存使用 |
139.87 MiB |
提交时间 |
2025-01-14 21:05:04 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 500010
#define inf 1e9
inline ll read(){
ll x=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x;
}
struct node_sgt{
ll l[MAXN*4],r[MAXN*4],minz[MAXN*4];
void push_up(ll now){
minz[now]=min(minz[now*2],minz[now*2+1]);
}
void build(ll dl,ll dr,ll now){
l[now]=dl,r[now]=dr,minz[now]=inf;
if(dl==dr)return;
ll mid=(dl+dr)/2;
build(dl,mid,now*2);
build(mid+1,dr,now*2+1);
}
ll find(ll dl,ll dr,ll now){
if(l[now]>=dl&&r[now]<=dr){
return minz[now];
}
ll mid=(l[now]+r[now])/2,ans=inf;
if(dl<=mid)ans=min(ans,find(dl,dr,now*2));
if(dr>mid)ans=min(ans,find(dl,dr,now*2+1));
return ans;
}
void insert(ll pos,ll val,ll now){
minz[now]=min(minz[now],val);
if(l[now]==r[now])return;
ll mid=(l[now]+r[now])/2;
if(pos<=mid)insert(pos,val,now*2);
else insert(pos,val,now*2+1);
}
}sgt;
ll fa[MAXN][50],dep[MAXN],v[MAXN];
ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
ll n,q,idx;
void build(ll x,ll y){
nxt[++idx]=hd[x];
ed[idx]=y;
hd[x]=idx;
}
void dfs(ll now,ll p){
fa[now][0]=p;
dep[now]=dep[p]+1;
for(int i=1;i<=30;i++){
fa[now][i]=fa[fa[now][i-1]][i-1];
}
for(int i=hd[now];i;i=nxt[i]){
ll y=ed[i];
if(y==p)continue;
dfs(y,now);
}
}
ll lca(ll x,ll y){
if(dep[x]<dep[y])swap(x,y);
for(int i=30;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]){
x=fa[x][i];
}
}
if(x==y)return x;
for(int i=30;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i],y=fa[y][i];
}
}
return fa[x][0];
}
int main(){
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
n=read();
for(int i=1;i<n;i++){
ll x=read(),y=read();
build(x,y);
build(y,x);
}
dfs(1,0);
sgt.build(1,n-1,1);
for(int i=1;i<n;i++){
v[i]=dep[lca(i,i+1)];
sgt.insert(i,v[i],1);
// cout<<v[i]<<" ";
}
// cout<<endl;
q=read();
for(int i=1;i<=q;i++){
ll l=read(),r=read(),k=read(),ans=-inf;
if(k==1){
for(int x=l;x<=r;x++)ans=max(ans,dep[x]);
}else{
for(int x=l;x+k-1<=r;x++){
ll y=x+k-1;
ans=max(ans,sgt.find(x,y-1,1));
}
}
cout<<ans<<endl;
}
return 0;
}