题解 | 冥古之潮

import java.util.*;

public class Main{
    static final int N = 1000005;
    static final int mod = 1000000007;
    static ArrayList<Integer>[] e = new ArrayList[N];
    static int[] dis = new int[N];
    static int[] headd = new int[N<<1];
    static int[] next = new int[N<<1];
    static int[] to = new int[N<<1];
    static int cnt = 0;
    public static void addage(int u, int v){
        cnt ++;
        next[cnt] = headd[u];
        to[cnt] = v;
        headd[u] = cnt;
    } 
    public static void bfs(int now){
        int[] queue = new int[N];
        int head = 0;
        int tail = 0;
        queue[tail++] = now;
        while(head < tail){
            int tmp = queue[head++];
            for(int j = headd[tmp]; j > 0; j = next[j]){
                int i = to[j];
                if(dis[i] != -1) continue;
                dis[i] = dis[tmp] + 1;
                queue[tail++] = i;
            }
        }
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        int x = in.nextInt();
        for(int i = 1; i <= n; i++){
            e[i] = new ArrayList<Integer>();
            dis[i] = -1;
        }
        for(int i = 1; i <= m; i++){
            int u = in.nextInt();
            int v = in.nextInt();
            addage(u, v);
            addage(v, u);
        }
        dis[x] = 0;
        bfs(x);
        int[] a = new int[n+5];
        int maxn = 0;
        for(int i = 1; i <= n; i++){
            if(i == x) continue;
            a[dis[i]] ++;
            maxn = Math.max(dis[i], maxn);
        }
        long[] f = new long[5005];
        f[0] = 1;
        for(int i = 1; i <= maxn; i++){
            if(a[i] == 0) continue;
            for(int j = 5000; j > 0 ; j--){
                f[j] = (f[j] + f[j-1]*a[i]%mod)%mod;
            }
        }
        while(q-- > 0){
            int k = in.nextInt();
            if(k > maxn){
                System.out.println(0);
                continue;
            }
            System.out.println(f[k]);
        }
    }
}