#include #include #include #include #include using namespace std; const int MAXK = 25; const int MAXN = 1e5 + 5; struct state { int dist; int vertex, fuel; }; bool operator <(const state A, const state B) { if(A.dist!=B.dist) return A.dist>B.dist; if(A.vertex!=B.vertex) return A.vertex graph[MAXN]; priority_queue q; vector answer; void DFS(int x, int newFuel, int newDist) { dist[x][newFuel] = newDist; q.push({newDist, x, newFuel}); if(newFuel==0) return; for(int i = 0;i newDist) { DFS(graph[x][i], newFuel-1, newDist); } } } void useState(int vertex, int fuel) { if(vertex==1) return; int toThis = dist[vertex][fuel]; if(dist[ d[vertex] ][min(fuel+1, k)] > toThis) { dist[ d[vertex] ][min(fuel+1, k)] = toThis; q.push({dist[ d[vertex] ][min(fuel+1, k)], d[vertex], min(fuel+1, k)}); } if(fuel!=0) { int newDist = toThis + 1; //if(last==true) newDist++; for(int i = 0;i newDist) { DFS(graph[vertex][i], fuel-1, newDist); //dist[ graph[vertex][i] ][fuel-1][false] = newDist; //q.push({newDist, graph[vertex][i], fuel-1, false}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); ifstream cin("space.in"); ofstream cout("space.out"); int Q; cin >> n >> m >> s >> k; for(int i = 2;i<=n;i++) { cin >> d[i]; } for(int i = 0;i> u >> v; graph[u].push_back(v); graph[v].push_back(u); } for(int i = 1;i<=n;i++) { for(int j = 0;j<=k;j++) { dist[i][j] = 25*MAXN; dist[i][j] = 25*MAXN; } } dist[s][1] = 0; q.push({0, s, 1}); while(q.empty()==false) { state curr = q.top();q.pop(); if(curr.dist!=dist[curr.vertex][curr.fuel]) continue; //cout << curr.vertex << " " << curr.fuel << " " << curr.last << //" --> " << curr.dist << '\n'; useState(curr.vertex, curr.fuel); } cin >> Q; while(Q--) { cin >> u; int curr = 25*MAXN; for(int i = 0;i<=k;i++) { if(dist[u][i]!=-1)curr = min(curr, dist[u][i]); if(dist[u][i]!=-1) curr = min(curr, dist[u][i]); } if(curr==25*MAXN) curr = -1; answer.push_back(curr); } cout << answer[0]; for(int i = 1;i