#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1e9 + 7;
const int Maxn = 3e3 + 10;
const ll Inf = 1000000000000000LL;
vector<pll> G[Maxn];
vector<pll> Q[Maxn];
vector<ll> R[Maxn];
ll ans[Maxn], dep[Maxn];
void DFS(ll u, ll d = 1){
dep[u] = d;
R[u].pb(0);
for(auto E : G[u]){
ll adj = E.F;
DFS(adj, d + E.S);
for(auto x : R[adj]) R[u].pb(x + E.S);
}
sort(all(R[u]));
R[u].resize(unique(all(R[u])) - R[u].begin());
}
ll s;
ll cnt[1000010];
bool check(ll x){
if(x < 0) return false;
return (cnt[x] > 0);
}
void DFS2(ll u){
for(auto x: R[u]) cnt[x] ++;
for(auto X : Q[u]){
ll x = X.F - dep[u];
//cerr << u << ' ' << X.F << ' ' << x << '\n';
if(x >= s + 1) ans[X.S] = (cnt[x - (s + 1)] > 0);
/*for(int i = 1; i * i <= x; i++){
if(x % i == 0){
ans[X.S] |= check(i - (s + 1));
ans[X.S] |= check((x / i) - (s + 1));
}
}*/
if(x == 0) ans[X.S] = true;
}
for(auto E : G[u]){
DFS2(E.F);
}
for(auto x : R[u]) cnt[x] --;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, m, k;
cin >> n >> m >> k >> s;
ll p, l;
for(int i = 1; i <= n; i++){
cin >> p >> l;
G[p].pb({i, l + (p != 0)});
}
for(int i = 1; i <= m; i++){
cin >> p >> l;
Q[p].pb({k - l - 1, i});
}
//cerr << '\n';
DFS(0);
DFS2(0);
for(int i = 1; i <= m; i++) cout << (ans[i] ? "YES\n" : "NO\n");
return 0;
}
/*
2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
8056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
