BZOJ2159 - Crash 的文明世界

BZOJ2159 - Click Here

  

Description

  Crash 小朋友最近迷上了一款游戏——文明5(Civilization V)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。现在Crash 已经拥有了一个N 个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此Crash 只修建了N-1 条道路连接这些城市,不过可以保证任意两个城市都有路径相通。在游戏中,Crash 需要选择一个城市作为他的国家的首都,选择首都需要考虑很多指标,有一个指标是这样的:

  其中S(i)表示第i 个城市的指标值,dist(i, j)表示第i 个城市到第j 个城市需要经过的道路条数的最小值,k 为一个常数且为正整数。因此Crash 交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数mod 10007 的值。

  

Input

  输入的第一行包括两个正整数N 和k。下面有N-1 行,每行两个正整数u、v (1 ≤ u, v ≤ N),表示第u 个城市和第v 个城市之间有道路相连。这些道路保证能符合题目的要求。

  

Output

  输出共N 行,每行一个正整数,第i 行的正整数表示第i 个城市的指标值 mod 10007 的值。

  

Solutions

  先讲个个人认为比较显然的做法。

  定义$S_d(i)$表示与$i$距离为$d$的节点数,则题目实则是求$\sum_d S_d(i) \cdot d^k$

  

  对于$i$的相邻节点$j$,有$\sum_d S_d(i) \cdot d^k = \sum_j \sum_d S_d(j) \cdot (d+1)^k$。

  考虑对右式展开

  令$f_k(i)=\sum_d S_d(i) \cdot d^k$,那么上式等价于$f_k(i) = \sum_j \sum_p \dbinom{k}{p} f_p(j)$

  因此,如果能够维护相邻接点的$f_p(j)$,则能够在$k^2$时间复杂度内求出$f_k(i)$

  

  考虑树形dp,对每个节点分别维护子树内的$f_p(i)$与非子树内$f_p(i)$,则能够利用上诉式子快速转移。

  时间复杂度$O(nk^2)$


  这题还有$O(nk)$做法,不过感觉没有上面做法自然,完全就是推公式…

  定义$S_d(i)$表示与$i$距离为$d$的节点数,那么有$ans = \sum_d S_d(i) \cdot d^k$

  

  考虑对右式展开

  其中$S(n,m)$表示第二类斯特林数。

  

  令$f_p(i) = \sum_d S_d(i) \dbinom{d}{p}$,则$ans = \sum_p S(k,p) \cdot p! \cdot f_p(i)$

  那么现在的问题就是求$f_p(i)$。对于$i$的相邻节点$j$,有

  

  同样的,考虑树形dp,分别维护子树与非子树的$f_p(i)$,并利用上式快速转移。

  时间复杂度$O(nk)$

  

CODE

CODE($O(nk)$做法) - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang