挑战全网最萌 noipt4 做法

· · 题解

由于某些原因，某字已被替换为"萌"。

显然的，区间 lca 就是相邻数对 lca 中 dep 最小的，所以问题转化为最大化区间内问长度为 k 的子区间的最小值。

直接二分这个最小值，把大于等于的当作 1，小于的当作 0，相当于询问区间内是否存在长度为 k 的 1 的连续段，可以用线段树维护区间最长连续段判断是否大于等于 k 即可，这个是可以整体二分的，注意要把相同的值离散化成不同的值，不然会同一个点有多次指针移动，时间复杂度 O(n\log^2 n)。

loj 可过，目测 ccf 机子也能过。

#include<bits/stdc++.h>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
void print(int x){
    if(x>9) print(x/10);
    *O++=x%10+'0';
}
const int N=5e5+4,K=20;
int n,q,fa[N],dep[N],cd[N],dfn[N],nfd[N],idx,st[N][K],lg[N],sz[N];
vector<int> g[N];
struct ququ{
    int l,r,k,id;
}qu[N];
ququ qq[N],qqq[N];
void dfs1(int x){
    dep[x]=dep[fa[x]]+1;
    nfd[dfn[x]=++idx]=x;
    sz[x]=1;
    for(auto y:g[x]){
        if(y==fa[x]) continue;
        fa[y]=x;
        dfs1(y);
        sz[x]+=sz[y];
    }
}
int get(int x,int y){return dep[x]<dep[y]?x:y;}
void init(){
    for(int i=1;i<=n;i++) st[dfn[i]][0]=i;
    for(int i=1;i<K;i++)
        for(int j=1;j+(1<<i)-1<=n;j++) st[j][i]=get(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
int qst(int l,int r){
    int len=lg[r-l+1];
    return get(st[l][len],st[r-(1<<len)+1][len]);
}
int lca(int x,int y){
    if(x==y) return x;

    if(dfn[x]>dfn[y]) swap(x,y);
    return fa[qst(dfn[x]+1,dfn[y])];
}
int ans[N];
struct node{
    int l,r,v,len;
    node operator +(const node b)const{
        node c;
        if(l==len) c.l=len+b.l;
        else c.l=l;
        if(b.r==b.len) c.r=b.len+r;
        else c.r=b.r;
        c.v=max(max(v,b.v),r+b.l);
        c.len=len+b.len;
        return c;
    }
}t[N<<1];
int a[N],b[N],d[N],e[N],cnt[N],f[N],m,qqqq;
void out(node x){
    cerr<<x.l<<" "<<x.r<<" "<<x.v<<" "<<x.len<<"\n";
}
int query(int l,int r){
    node ansl,ansr;
    bool fl=0,fr=0;
    for(l+=m-1,r+=m;l<r;l>>=1,r>>=1){
        if(l&1){
            if(!fl) ansl=t[l++],fl=1;
            else ansl=ansl+t[l++];
        }
        if(r&1){
            if(!fr) ansr=t[--r],fr=1;
            else ansr=t[--r]+ansr;
        }
    }
    if(!fl) return ansr.v;
    if(!fr) return ansl.v;
    return (ansl+ansr).v;
}
void update(int x,int v){
    x+=m-1;
    t[x]={v,v,v,1};
    for(x>>=1;x;x>>=1)
        t[x]=t[x<<1]+t[x<<1|1];
}
int last;
void ef(int l,int r,int L,int R){
    if(L>R) return;
    if(l==r){
        for(int i=L;i<=R;i++)
            ans[qq[i].id]=f[l];
        return;
    }
    int mid=(l+r+1)>>1;
    while(last>mid)
        update(e[--last],1);
    while(last<mid)
        update(e[last++],0);
    int M=L,rr=R;
    for(int i=L;i<=R;i++){
        int res=query(qq[i].l,qq[i].r);
        if(res<qq[i].k) qqq[M++]=qq[i];
        else qqq[rr--]=qq[i];
    }
    for(int i=L;i<=R;i++) qq[i]=qqq[i];
    ef(l,mid-1,L,M-1);
    ef(mid,r,rr+1,R);
}
void solve(){
    last=1;
    for(int i=1;i<=m;i++) t[i+m-1]={1,1,1,1};
    for(int i=m-1;i;i--) t[i]=t[i<<1]+t[i<<1|1];
    ef(1,n-1,1,qqqq);
    for(int i=1;i<=q;i++) print(ans[i]),*O++=10;
}
namespace sgt{
    int t[N<<1];
    void init(){
        for(int i=1;i<=n;i++) t[i+n-1]=dep[i];
        for(int i=n-1;i;i--) t[i]=max(t[i<<1],t[i<<1|1]);
    }
    int query(int l,int r){
        int ans=0;
        for(l+=n-1,r+=n;l<r;l>>=1,r>>=1){
            if(l&1) ans=max(ans,t[l++]);
            if(r&1) ans=max(ans,t[--r]);
        }
        return ans;
    }
}
signed main(){
    // freopen("query.in","r",stdin);
    // freopen("query.out","w",stdout);
    n=read();
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1,x,y;i<n;i++){
        x=read(),y=read();
        g[x].push_back(y),g[y].push_back(x);
    }
    dfs1(1);
    init();
    for(int i=1;i<n;i++) b[i]=a[i]=dep[lca(i,i+1)];
    m=n-1;
    sort(b+1,b+m+1);
    m=unique(b+1,b+m+1)-b-1;
    for(int i=1;i<=m;i++)
        d[b[i]]=i;
    for(int i=1;i<n;i++) cnt[d[a[i]]]++;
    for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
    for(int i=1;i<n;i++){
        int k=d[a[i]];
        a[i]=cnt[d[a[i]]]--;
        f[a[i]]=b[k];
    }
    m=n-1;
    sgt::init();
    for(int i=1;i<n;i++) e[a[i]]=i;
    q=read();
    for(int i=1;i<=q;i++){
        int l=read(),r=read(),k=read();
        if(l==r){
            ans[i]=dep[l];
            continue;
        }
        if(k==1){
            ans[i]=sgt::query(l,r);
            continue;
        }
        r--,k--;
        qq[++qqqq]={l,r,k,i};
    }
    solve();
    fwrite(obuf,O-obuf,1,stdout);
    return 0;
}