自动搬运

查看原文

来自洛谷，原作者为

	Shunpower 我笨笨的，菜菜的，累累的 >_< | 在役

搬运于2025-08-24 23:16:34，当前版本为作者最后更新于2025-07-28 20:06:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

来点暴力。

考虑把路径拆成两半分开做，我们本质上是想查一条直上直下路径上第一个点 $i$ 满足（这里的例子是向上）：

$dis$ 表示根到某个点的距离。向下的一侧 $dis_u-dis_i$ 是反过来的。

这个问题直接搞比较难做，考虑拆开第一个条件变成 $a_i<a_Q$ 和 $a_Q<a_i$ 做两遍再取较近的一个。这样相当于一个询问有四块问题，每个是找一条直上直下路径上满足某个二维偏序的最近点。我们直接离线第一维比较简单的颜色，然后树剖用线段树维护第二维，查询时二分即可。

直接朴素树剖套线段树上二分会产生 3log。但是这里的二分非常朴实无华，就是查左或右第一个小于等于某个定值的位置。所以可以用 1log 的线段树上二分来写，这样就做到 2log 了。

做法很暴力，常数略大，但是能过。不知道为什么跑得还比 @lzyqwq 老哥的有脑子做法快，可能是树剖太厉害了。

int n,m;
vector <pii> p[N];
int c[N],t[N];
vector <int> col[N];
struct queries{
    int u,v,col;
    ll T;
    bool up;
    int id;
} Q[N<<1];
int tqt;
vector <int> ans[N];
int tot;
int dep[N],siz[N],dfn[N],bac[N],top[N],hson[N];
ll wu[N],wd[N];
ll dis[N];
int f[N][18];
int U[N];
int LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int k=dep[u]-dep[v];
    fr2(i,17,0){
        if(k>=(1<<i)) u=f[u][i],k-=(1<<i);
    }
    if(u==v) return u;
    fr2(i,17,0){
        if(f[u][i]!=f[v][i]){
            u=f[u][i];
            v=f[v][i];
        }
    }
    return f[u][0];
}
void dfs1(int x,int fa){
    f[x][0]=fa;
    wu[x]=t[x]+dis[x];
    wd[x]=t[x]-dis[x];
    siz[x]=1;
    dep[x]=dep[fa]+1;
    int idx=0;
    for(auto y:p[x]){
        if(y.fi==fa) continue;
        dis[y.fi]=dis[x]+y.se;
        dfs1(y.fi,x);
        siz[x]+=siz[y.fi];
        if(siz[y.fi]>siz[idx]) idx=y.fi;
    }
    hson[x]=idx;
}
void dfs2(int x,int tp,int fa){
    tot++;
    dfn[x]=tot,bac[tot]=x;
    top[x]=tp;
    if(hson[x]) dfs2(hson[x],tp,x);
    for(auto y:p[x]){
        if(y.fi==fa||y.fi==hson[x]) continue;
        dfs2(y.fi,y.fi,x);
    }
}
#define mid (l+r>>1)
struct SGT{
    ll minn[N<<2];
    void pushup(int p){
        minn[p]=min(minn[p<<1],minn[p<<1|1]);
    }
    void build(int p,int l,int r){
        minn[p]=4e18;
        if(l==r) return;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }
    void insert(int p,int l,int r,int d,ll x){
        if(l==r) return minn[p]=x,void();
        if(d<=mid) insert(p<<1,l,mid,d,x);
        else insert(p<<1|1,mid+1,r,d,x);
        pushup(p);
    }
    int lefbinary(int p,int l,int r,int T){
        if(minn[p]>T) return -1;
        if(l==r) return l;
        if(minn[p<<1]<=T) return lefbinary(p<<1,l,mid,T);
        else return lefbinary(p<<1|1,mid+1,r,T);
    }
    int rigbinary(int p,int l,int r,int T){
        if(minn[p]>T) return -1;
        if(l==r) return l;
        if(minn[p<<1|1]<=T) return rigbinary(p<<1|1,mid+1,r,T);
        else return rigbinary(p<<1,l,mid,T);
    }
    vector <pair<int,pii>> segs;
    void findsegs(int p,int l,int r,int ml,int mr){
        if(ml<=l&&r<=mr) return segs.push_back({p,{l,r}}),void();
        if(ml<=mid) findsegs(p<<1,l,mid,ml,mr);
        if(mid<mr) findsegs(p<<1|1,mid+1,r,ml,mr);
    }
    int LB(int l,int r,int T){
        segs.clear();
        findsegs(1,1,n,l,r);
        fr1(i,0,(int)segs.size()-1){
            if(minn[segs[i].fi]>T) continue;
            return lefbinary(segs[i].fi,segs[i].se.fi,segs[i].se.se,T);
        }
        return -1;
    }
    int RB(int l,int r,int T){
        segs.clear();
        findsegs(1,1,n,l,r);
        fr2(i,(int)segs.size()-1,0){
            if(minn[segs[i].fi]>T) continue;
            return rigbinary(segs[i].fi,segs[i].se.fi,segs[i].se.se,T);
        }
        return -1;
    }
} Tu,Td;
int Gfu(int u,int v,int T){
    while(top[u]!=top[v]){
        int x=Tu.RB(dfn[top[u]],dfn[u],T);
        if(x!=-1) return bac[x];
        u=f[top[u]][0];
    }
    int x=Tu.RB(dfn[v],dfn[u],T);
    if(x!=-1) return bac[x];
    return -1;
}
int Gfd(int u,int v,int T){
    int ans=-1;
    while(top[u]!=top[v]){
        int x=Td.LB(dfn[top[v]],dfn[v],T);
        if(x!=-1) ans=x;
        v=f[top[v]][0];
    }
    int x=Td.LB(dfn[u],dfn[v],T);
    if(x!=-1) ans=x;
    if(ans==-1) return -1;
    return bac[ans];
}
ll Dis(int u,int v){
    return dis[u]+dis[v]-2ll*dis[LCA(u,v)];
}
#undef mid
int main(){
#ifdef Ltp
    freopen("hack.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n;
    fr1(i,2,n){
        int f,d;
        cin>>f>>d;
        p[f].pb(mp(i,d));
        p[i].pb(mp(f,d));
    }
    fr1(i,1,n) cin>>c[i],col[c[i]].pb(i);
    fr1(i,1,n) cin>>t[i];
    dfs1(1,1);
    dfs2(1,1,1);
    fr1(j,1,17) fr1(i,1,n) f[i][j]=f[f[i][j-1]][j-1];
    cin>>m;
    fr1(i,1,m){
        int u,v,b,t;
        cin>>u>>v>>b>>t;
        U[i]=u;
        int lca=LCA(u,v);
        tqt++;
        Q[tqt]={u,lca,b,t+dis[u],1,i};
        tqt++;
        Q[tqt]={lca,v,b,t+dis[u]-dis[lca]*2,0,i};
    }
    Tu.build(1,1,n);
    Td.build(1,1,n);
    sort(Q+1,Q+tqt+1,[](queries &x,queries &y){
        return x.col<y.col;
    });
    int poi=0;
    fr1(i,1,n){
        while(Q[poi+1].col<=i&&poi+1<=tqt){
            poi++;
            if(Q[poi].up){
                int x=Gfu(Q[poi].u,Q[poi].v,Q[poi].T);
                if(~x) ans[Q[poi].id].pb(x);
            }
            else{
                int x=Gfd(Q[poi].u,Q[poi].v,Q[poi].T);
                if(~x) ans[Q[poi].id].pb(x);
            }
        }
        // cerr<<"!"<<endl;
        for(auto j:col[i]){
            Tu.insert(1,1,n,dfn[j],wu[j]);
            Td.insert(1,1,n,dfn[j],wd[j]);
        }
    }
    Tu.build(1,1,n);
    Td.build(1,1,n);
    poi=tqt+1;
    fr2(i,n,1){
        while(Q[poi-1].col>=i&&poi-1>=1){
            poi--;
            if(Q[poi].up){
                int x=Gfu(Q[poi].u,Q[poi].v,Q[poi].T);
                if(~x) ans[Q[poi].id].pb(x);
            }
            else{
                int x=Gfd(Q[poi].u,Q[poi].v,Q[poi].T);
                if(~x) ans[Q[poi].id].pb(x);
            }
        }
        for(auto j:col[i]){
            Tu.insert(1,1,n,dfn[j],wu[j]);
            Td.insert(1,1,n,dfn[j],wd[j]);
        }
    }
    fr1(i,1,m){
        if(ans[i].empty()) cout<<-1<<'\n';
        else{
            sort(ans[i].begin(),ans[i].end(),[i](int &x,int &y){
                return Dis(U[i],x)<Dis(U[i],y);
            });
            cout<<ans[i][0]<<'\n';
        }
    }
    ET;
}
//ALL FOR Zhang Junhao.