結果

問題 No.827 総神童数
ユーザー ks2m
提出日時 2019-05-03 23:12:12
言語 Java
(openjdk 23)
結果
RE  
実行時間 -
コード長 1,960 bytes
コンパイル時間 2,563 ms
コンパイル使用メモリ 79,428 KB
実行使用メモリ 203,632 KB
最終ジャッジ日時 2024-12-31 19:05:46
合計ジャッジ時間 61,605 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 19 RE * 1 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
		for (int i = 0; i < n - 1; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();

			List<Integer> list1 = map.get(u);
			if (list1 == null) {
				list1 = new ArrayList<Integer>();
				map.put(u, list1);
			}
			list1.add(v);

			List<Integer> list2 = map.get(v);
			if (list2 == null) {
				list2 = new ArrayList<Integer>();
				map.put(v, list2);
			}
			list2.add(u);
		}
		sc.close();

		int[] dep = new int[n + 1];
		Queue<Integer> que = new ArrayDeque<Integer>();
		que.add(1);
		dep[1] = 1;
		while (!que.isEmpty()) {
			Integer cur = que.poll();
			List<Integer> list = map.get(cur);
			for (Integer next : list) {
				if (dep[next] == 0) {
					que.add(next);
					dep[next] = dep[cur] + 1;
				}
			}
		}

		TreeMap<Integer, Integer> depMap = new TreeMap<Integer, Integer>();
		for (int i = 1; i <= n; i++) {
			int key = dep[i];
			if (depMap.containsKey(key)) {
				depMap.put(key, depMap.get(key) + 1);
			} else {
				depMap.put(key, 1);
			}
		}

		int mod = 1000000007;
		long p = 1;
		int i = 1;
		long ans = 0;
		while (!depMap.isEmpty()) {
			Entry<Integer, Integer> ent = depMap.pollLastEntry();
			int k = ent.getKey();
			int v = ent.getValue();
			for ( ; i <= n - k; i++) {
				p *= i;
				p %= mod;
			}
			long npr = nPr(n, k);
			ans += npr * p / k % mod * v % mod;
			ans %= mod;
		}
		System.out.println(ans);
	}

	static long nPr(long n, long r) {
		long m = 1000000007;
		long val = 1;
		for (int i = 1; i <= r; i++) {
			val = val * (n - i + 1) % m;
		}
		return val;
	}
}
0