| 记录编号 |
599576 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[NOIP 2024]树上查询 |
最终得分 |
100 |
| 用户昵称 |
 flyfree |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
25.117 s |
| 提交时间 |
2025-03-24 16:29:24 |
内存使用 |
165.17 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug cout<<"flyfree\n";
#define MAXN 500010
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct node_Sagtr{
ll l[MAXN*4],r[MAXN*4],maxz[MAXN*4];
void build(ll now,ll lz,ll rz){
l[now]=lz,r[now]=rz,maxz[now]=0;
if(lz==rz)return;
ll mid=(lz+rz)/2;
build(now*2,lz,mid);
build(now*2+1,mid+1,rz);
}
void push_up(ll now){
maxz[now]=max(maxz[now*2],maxz[now*2+1]);
}
void insert(ll now,ll p,ll val){
if(l[now]==r[now]){
maxz[now]=max(maxz[now],val);
return;
}
ll mid=(l[now]+r[now])/2;
if(p<=mid)insert(now*2,p,val);
else insert(now*2+1,p,val);
push_up(now);
}
ll find(ll now,ll lz,ll rz){
if(l[now]>=lz&&r[now]<=rz)return maxz[now];
ll mid=(l[now]+r[now])/2,ans=0;
if(lz<=mid)ans=max(ans,find(now*2,lz,rz));
if(rz>mid)ans=max(ans,find(now*2+1,lz,rz));
return ans;
}
};
ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
ll n,m,idx;
ll dep[MAXN],fa[MAXN][50],v[MAXN];
ll l[MAXN],r[MAXN];
struct node{
ll l,r,v,id,ans;
};
node qs[MAXN],line[MAXN];
bool cmp_r(node a,node b){
return a.r>b.r;
}
bool cmp_l(node a,node b){
return a.l<b.l;
}
bool cmp_len(node a,node b){
return a.r-a.l>b.r-b.l;
}
bool cmp_id(node a,node b){
return a.id<b.id;
}
bool cmp_k(node a,node b){
return a.v>b.v;
}
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<=20;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=20;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
deque <pair<ll,ll> > q;
node_Sagtr tr;
//void work_l(){
// sort(qs+1,qs+1+m,cmp_l);
// sort(line+1,line+n,cmp_l);
// ll now=1;
// tr.build(1,1,n);
// for(int i=1;i<=m;i++){
// while(now<n){
// if(line[now].l<=qs[i].l){
// tr.insert(1,line[now].r,line[now].v);
// now++;
// }else break;
// }
// qs[i].ans=max(qs[i].ans,tr.find(1,qs[i].l+qs[i].v-1,qs[i].r));
// }
//}
void work_r(){
sort(qs+1,qs+1+m,cmp_r);
sort(line+1,line+n,cmp_r);
ll now=1;
tr.build(1,1,n);
for(int i=1;i<=m;i++){
// cout<<i<<endl;
while(now<n){
if(line[now].r>=qs[i].r){
tr.insert(1,line[now].l,line[now].v);
now++;
}else break;
}
qs[i].ans=max(qs[i].ans,tr.find(1,1,qs[i].r-qs[i].v+1));
}
}
void work_len(){
sort(qs+1,qs+1+m,cmp_k);
sort(line+1,line+n,cmp_len);
ll now=1;
tr.build(1,1,n);
for(int i=1;i<=m;i++){
if(qs[i].v==1&&qs[i-1].v>1){
for(int j=1;j<=n;j++)tr.insert(1,j,dep[j]);
}
while(now<n){
if(line[now].r-line[now].l+1>=qs[i].v){
tr.insert(1,line[now].r,line[now].v);
now++;
}else break;
}
qs[i].ans=max(qs[i].ans,tr.find(1,qs[i].l+qs[i].v-1,qs[i].r));
}
}
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);
}
// debug;
dfs(1,0);
// debug;
for(int i=1;i<n;i++)v[i]=dep[lca(i,i+1)];
q.push_back(make_pair(0,0));
for(int i=1;i<n;i++){
// cout<<i<<" "<<v[i]<<endl;
while(!q.empty()&&q.back().second>=v[i])q.pop_back();
l[i]=q.back().first+1;
q.push_back(make_pair(i,v[i]));
}
// debug;
while(!q.empty())q.pop_back();
q.push_back(make_pair(n,0));
for(int i=n-1;i;i--){
while(!q.empty()&&q.back().second>=v[i])q.pop_back();
r[i]=q.back().first;
q.push_back(make_pair(i,v[i]));
}
// debug;
for(int i=1;i<=n-1;i++){
line[i].l=l[i],line[i].r=r[i],line[i].v=v[i];
// cout<<"i:"<<i<<" dep:"<<v[i]<<endl;
}
m=read();
for(int i=1;i<=m;i++){
qs[i].l=read(),qs[i].r=read(),qs[i].v=read(),qs[i].id=i;
}
// work_l();
work_r();
work_len();
sort(qs+1,qs+1+m,cmp_id);
// for(int i=1;i<=m;i++)cout<<qs[i].ans<<endl;
for(int i=1;i<=m;i++)printf("%lld\n",qs[i].ans);
return 0;
}