题目传送门

简简单单的 DFS 操作

有两种情况：

情况1：

走到任意一个点，然后运用链接跳到 $o$ 的某个祖先 $y$ 再走到 $o$。枚举所有 $y$ 看看是否存在 $x$ 即可。时间复杂度 $O(nm)$。

情况2：

走到 $o$ 的某个祖先 $x$，然后走到 $x$ 子树内某个点 $y$，在 $x$ 和 $y$ 之间不断通过用链接来回走，最后再从 $x$ 走到 $o$。枚举 $x$ 和 $y$ 维护出每个长度是否可能存在，然后枚举约数判断是否存在对应的 $x$ 和 $y$ 即可。

AC 代码：

#include<iostream>
using namespace std;
#define N 3010
int n,m,K,S,i,x,a[N],len[N],g[N],G[N],v[N<<1],nxt[N<<1],ed;
int q[N],t,st[N],en[N],dfn,seq[N],f[2000010];
bool ans[N];
void add(int&x,int y){v[++ed]=y;nxt[ed]=x;x=ed;}
void dfs1(int x){
 q[++t]=a[x];
 seq[st[x]=++dfn]=a[x];
 for(int i=G[x];i;i=nxt[i]){
   int o=v[i];
   for(int j=1;j<=t;j++){
     int k=K-S-a[x]-len[o]+q[j];
     if(k>=0&&k<=K)if(f[k]){ans[o]=1;break;}
   }
 }
 for(int i=g[x];i;i=nxt[i])dfs1(v[i]);
 t--;
 en[x]=dfn;
}
void dfs2(int x){
 for(int i=st[x];i<=en[x];i++)f[seq[i]-a[x]+S]++;
 for(int i=G[x];i;i=nxt[i]){
   int o=v[i];
   if(ans[o])continue;
   int k=K-a[x]-len[o];
   for(int j=1;j*j<=k;j++)if(k%j==0)if(f[j]||f[k/j]){ans[o]=1;break;}
 }
 for(int i=g[x];i;i=nxt[i])dfs2(v[i]);
 for(int i=st[x];i<=en[x];i++)f[seq[i]-a[x]+S]--;
}
int main(){
 scanf("%d%d%d%d",&n,&m,&K,&S);S++;
 for(i=1;i<=n;i++){
   scanf("%d%d",&x,&a[i]);
   a[i]+=a[x]+1;
   add(g[x],i);
 }
 for(i=1;i<=m;i++){
   scanf("%d%d",&x,&len[i]);
   len[i]++;
   ans[i]=a[x]+len[i]==K;
   if(!ans[i])
     	add(G[x],i);
 }
 for(i=0;i<=n;i++)
   f[a[i]]=1;
 dfs1(0);
 for(i=0;i<=n;i++)
   f[a[i]]=0;
 dfs2(0);
 for(i=1;i<=m;i++)
   puts(ans[i]?"YES":"NO");
 return 0;
}

引用