Universal Cup Judging System

Universal Cup

Süre Sınırı: 4.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

頂点 $1$ を根とする $n$ 頂点の木を考えます。木内の各頂点 $i$ には重み $p_i$ があり、$p_1, p_2, \dots, p_n$ は順列をなします。

$L_{u,v}$ を頂点 $u$ から頂点 $v$ への単純パス上($u$ と $v$ を含む)にある任意の頂点の重みの最大値とします。$\operatorname{subtree}(i)$ を頂点 $i$ の部分木を構成する頂点の集合とします。$S_i = \{u \mid u \in \operatorname{subtree}(i) \land L_{u,i} \le p_i\}$ と定義します。これは、$i$ から出発して子への移動のみを行い、重みが $p_i$ 以下の頂点のみを通って到達できる頂点の集合です。$f_i = |S_i|$ をその頂点集合のサイズとします。

頂点の値を $q_{f_i}$ と定義します。ここで、$q$ は与えられた値列 $q_1, q_2, \dots, q_n$ です。

各組 $(i, j)$ について、$p_i = j$ を満たすすべての重み配置にわたる頂点 $i$ の値の総和を求めたいです。答えは非常に大きくなる可能性があるため、結果を $10^9 + 7$ で割った余りを出力してください。

入力

1 行目には、木の頂点数を表す 1 つの整数 $n$ ($1 \le n \le 700$) が与えられます。

次の行には、$q_1, q_2, \dots, q_n$ ($0 \le q_i < 10^9 + 7$) を表す $n$ 個の整数が与えられます。

続く $n - 1$ 行には、それぞれ木の辺を表す 2 つの整数 $u, v$ が与えられます。

出力

$n$ 行を出力し、各行には $n$ 個の整数を含めてください。$i$ 行目の $j$ 番目の整数は、対応する答えを $10^9 + 7$ で割った余りを表します。

入出力例

入力 1

3
1 1 2
1 2
2 3

出力 1

2 2 4
2 2 2
2 2 2

入力 2

4
1 2 3 4
1 2
2 3
1 4

出力 2

6 10 16 24
6 8 10 12
6 6 6 6
6 6 6 6

入力 3

7
3 7 2 4 1 8 9
1 2
1 3
2 4
4 5
3 6
4 7

出力 3

2160 3120 3168 2952 2160 3720 6480
2160 2640 2640 2412 2208 2280 2880
2160 2640 3120 3600 4080 4560 5040
2160 3120 3648 3744 3408 2640 1440
2160 2160 2160 2160 2160 2160 2160
2160 2160 2160 2160 2160 2160 2160
2160 2160 2160 2160 2160 2160 2160

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1702EditorialOpenAnother SolutionMilmonView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.