现代汽车前瞻杯-2025牛客暑期多校训练营3 ——Head out to the Target · znzryb
## 思路讲解
我们赛时设计了一个算法
```cpp
vll siz(N+5,0);
vector<pll> nodes(N+5,{0,0});
FOR(i,1,K){
ll u,l,r;
cin>>u>>l>>r;
siz[u]=r-l+1;
nodes[u]={l,r};
}
function<void(ll)> dfs=[&](ll u)->void{
for(auto &v:g[u]){
dfs(v);
siz[u]+=siz[v];
}
};
```
但是这个算法只能判断可达性（或者可达性都有点问题），瓶颈在于这个算法并不在乎达到该节点的时间。
那么有没有办法让这个算法在乎时间那？其实也简单，在该时间内，该树只有之前能到达的点。
```cpp
ll mn=min(time,dis);
ll v=tr.findk(u,dis-mn);
if(v==u){ // 找到可到达点
ll ans=dis+l-1;
cout<<ans<<"\n";
return;
}
while(v!=low){ // 溯源路径，给路径上面所有点打上OK标记
tr.OK[v]=true;
v=tr.fa[v][0];
}
```
## AC代码
::: 源代码
```cpp
// Problem: Head out to the Target
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/108300/H
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
// by Gospel_rock
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,A[MAXN],F[MAXN];
/*
*/
struct STtree{
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
using ll=long long;
ll n;
vector<vector<ll> > fa,g;
vector<ll> dep;vector<bool> OK;
STtree(ll n){
this->n=n;
fa.resize(n+5,vector<ll>(35,0));
dep.resize(n+5,0);
OK.resize(n+5,0);
g.resize(n+5);
}
// ST 表
void dfs(ll u,ll p){
fa[u][0]=p;
dep[u]=dep[p]+1;
for(auto &v:g[u]){
if(v==p) continue;
dfs(v,u);
}
}
ll findk(ll u,ll k){ // 找到u的第k个祖先（父节点是第一个祖先）
if(k==0) return u;
ROF(i,30,0){
if(k>>i&1){ // 如果k的二进制表示中第i位是1，就向上跳2^i步
u=fa[u][i];
}
}
return u;
}
// 无法正确处理这个点已经被到达的情况
ll findlow(ll u){ // 找到最低的合法点（即OK=true的点）
if(OK[u]) return u;
ROF(i,30,0){
// 去找到最高的不合法点
if(fa[u][i] && !OK[fa[u][i]]){
u=fa[u][i];
}
}
return fa[u][0];
}
void add(ll u,ll v){
g[u].push_back(v);
g[v].push_back(u);
}
void work(ll root=1){
OK[0]=true;OK[1]=true;
dfs(root,0);
FOR(u,1,n){
FOR(i,1,__lg(dep[u])){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
}
}
// #ifdef LOCAL
// void DEBUG(){ // 对ST表debug
// FOR(i,1,N){
// FOR(j,0,15){
// cerr<<fa[i][j]<<" ";
// }
// cerr<<"\n";
// }
// }
// #endif
};
inline void __();
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--)
__();
return 0;
}
inline void __(){
cin>>N>>K;
STtree tr(N);
FOR(i,2,N){
cin>>F[i];
tr.add(F[i],i);
}
tr.work();
FOR(i,1,K){
ll u,l,r;
cin>>u>>l>>r;
ll low=tr.findlow(u);
if(low==u){
cout<<l<<"\n";
return;
}
ll dis=tr.dep[u]-tr.dep[low],time=r-l+1;
ll cnt=0;
ll mn=min(time,dis);
ll v=tr.findk(u,dis-mn);
if(v==u){
ll ans=dis+l-1;
cout<<ans<<"\n";
return;
}
while(v!=low){
tr.OK[v]=true;
v=tr.fa[v][0];
}
// #ifdef LOCAL
// FOR(i,1,N){
// cerr<<tr.OK[i]<<" ";
// }
// cerr<<"\n";
// #endif
}
cout<<-1<<"\n";
}
/*
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78432470
*/
```
:::
## 心路历程（WA，TLE，MLE……）