题解：P12577 [UOI 2021] 树上的强盗
Shunpower
·
·
题解
来点暴力。
考虑把路径拆成两半分开做，我们本质上是想查一条直上直下路径上第一个点 i 满足（这里的例子是向上）：
a_i\ne a_Q\\
T_Q+dis_u-dis_i\ge t_i
这个问题直接搞比较难做，考虑拆开第一个条件变成 $a_i<a_Q$ 和 $a_Q<a_i$ 做两遍再取较近的一个。这样相当于一个询问有四块问题，每个是找一条直上直下路径上满足某个二维偏序的最近点。我们直接离线第一维比较简单的颜色，然后树剖用线段树维护第二维，查询时二分即可。
直接朴素树剖套线段树上二分会产生 3log。但是这里的二分非常朴实无华，就是查左或右第一个小于等于某个定值的位置。所以可以用 1log 的线段树上二分来写，这样就做到 2log 了。
做法很暴力，常数略大，但是能过。不知道为什么跑得还比 @lzyqwq 老哥的有脑子做法快，可能是树剖太厉害了。
```cpp
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.
```