#2159. 「国家集训队」Crash 的文明世界

「国家集训队」Crash 的文明世界

题目描述

Crash 小朋友最近迷上了一款游戏——文明 5(Civilization V)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。

现在 Crash 已经拥有了一个 nn 个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此 Crash 只修建了 n1n-1 条道路连接这些城市,不过可以保证任意两个城市都有路径相通。

在游戏中,Crash 需要选择一个城市作为他的国家的首都,选择首都需要考虑很多指标,有一个指标是这样的:

S(i)=j=1ndist(i,j)kS(i)=\sum_{j=1}^n \operatorname{dist}(i,j)^k

其中 S(i)S(i) 表示第 ii 个城市的指标值,dist(i,j)\operatorname{dist}(i, j) 表示第 ii 个城市到第 jj 个城市需要经过的道路条数的最小值,kk 为一个常数且为正整数。

因此 Crash 交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数 mod  10007\bmod\; 10007 的值。

输入格式

输入的第一行包括两个正整数 nnkk

下面有 n1n-1 行,每行两个正整数 u,v(1u,vn)u,v (1 \leq u, v \leq n),表示第 uu 个城市和第 vv 个城市之间有道路相。这些道路保证能符合题目的要求。

输出格式

输出共 nn 行,每行一个正整数,第 ii 行的正整数表示第 ii 个城市的指标值 mod  10007\bmod\; 10007 的值。

样例输入

5 2
1 2
1 3
2 4
2 5

样例输出

10
7
23
18
18

数据规模与约定

20%20\% 的数据满足 n5×103n \leq 5\times 10^3k30k \leq 30

50%50\% 的数据满足 n5×104n \leq 5\times 10^4k30k \leq 30

100%100\% 的数据满足 n5×104n \leq 5\times 10^4k150k \leq 150

【特别注意】 由于数据大小限制为 5MB,我只好对测试时的输入文件进行压缩处理。下面的函数可以将压缩的输入文件转化为原始输入文件。(函数从 infile 中读入压缩的输入文件,将解压缩后的输入文件输出到 outfile 中)

C/C++ 版本:

void Uncompress(FILE *infile, FILE *outfile) {
  int N, k, L, i, now, A, B, Q, tmp;
  fscanf(infile, "%d%d%d", &N, &k, &L);
  fscanf(infile, "%d%d%d%d", &now, &A, &B, &Q);
  fprintf(outfile, "%d %d\n", N, k);
  for (i = 1; i < N; i ++) {
    now = (now * A + B) % Q;
	tmp = (i < L) ? i : L;
	fprintf(outfile, "%d %d\n", i - now % tmp, i + 1);
  }
}

Pascal 版本:

procedure Uncompress(var infile, outfile : text);
var N, k, L, i, now, A, B, Q, tmp : longint; begin
  read(infile, N, k, L, now, A, B, Q);
  writeln(outfile, N, ' ', k);
  for i := 1 to N - 1 do begin
	now := (now * A + B) mod Q;
	if i < L then tmp := i
	else tmp := L;
	writeln(outfile, i - now mod tmp, ' ', i + 1);
  end;
end;

下面给出一个具体的例子。civiliazation_compressed.in表示压缩的输入文件, civilization.in表示解压缩后的输入文件。

civilization_compressed.in

7 26 4 29643 2347 5431 54209

civilization.in

7 26
1 2
2 3
2 4
3 5
4 6
5 7

2016.2.19 重设时限为 10s