A - Circle Pond

Time Limit: 2 sec / Memory Limit: 1024 MB

﻿配点 : 100

### 制約

• 1 \leq R \leq 100
• 入力は全て整数である。

### 入力

R


### 入力例 1

1


### 出力例 1

6.28318530717958623200


10^{-2} 以下の絶対誤差・相対誤差が許容されるので、 6.28 も正解になりますが、6 は不正解となります。

### 入力例 2

73


### 出力例 2

458.67252742410977361942


Score : 100 points

### Problem Statement

Print the circumference of a circle of radius R.

### Constraints

• 1 \leq R \leq 100
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

R


### Output

Print the circumference of the circle. Your output is considered correct if and only if its absolute or relative error from our answer is at most 10^{-2}.

### Sample Input 1

1


### Sample Output 1

6.28318530717958623200


Since we accept an absolute or relative error of at most 10^{-2}, 6.28 is also an acceptable output, but 6 is not.

### Sample Input 2

73


### Sample Output 2

458.67252742410977361942

B - Homework

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

ただし、夏休み中に全ての宿題を終わらせることができないときは、かわりに -1 を出力してください。

### 制約

• 1 \leq N \leq 10^6
• 1 \leq M \leq 10^4
• 1 \leq A_i \leq 10^4

### 入力

N M
A_1 ... A_M


### 入力例 1

41 2
5 6


### 出力例 1

30


### 入力例 2

10 2
5 6


### 出力例 2

-1


### 入力例 3

11 2
5 6


### 出力例 3

0


### 入力例 4

314 15
9 26 5 35 8 9 79 3 23 8 46 2 6 43 3


### 出力例 4

9


Score : 200 points

### Problem Statement

Takahashi has N days of summer vacation.

His teacher gave him M summer assignments. It will take A_i days for him to do the i-th assignment.

He cannot do multiple assignments on the same day, or hang out on a day he does an assignment.

What is the maximum number of days Takahashi can hang out during the vacation if he finishes all the assignments during this vacation?

If Takahashi cannot finish all the assignments during the vacation, print -1 instead.

### Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 10^4
• 1 \leq A_i \leq 10^4

### Input

Input is given from Standard Input in the following format:

N M
A_1 ... A_M


### Output

Print the maximum number of days Takahashi can hang out during the vacation, or -1.

### Sample Input 1

41 2
5 6


### Sample Output 1

30


For example, he can do the first assignment on the first 5 days, hang out on the next 30 days, and do the second assignment on the last 6 days of the vacation. In this way, he can safely spend 30 days hanging out.

### Sample Input 2

10 2
5 6


### Sample Output 2

-1


He cannot finish his assignments.

### Sample Input 3

11 2
5 6


### Sample Output 3

0


He can finish his assignments, but he will have no time to hang out.

### Sample Input 4

314 15
9 26 5 35 8 9 79 3 23 8 46 2 6 43 3


### Sample Output 4

9

C - management

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 人の社員からなる会社があり、各社員には 1,...,N の社員番号が割り当てられています。

X さんが Y さんの直属の上司であるとき、Y さんは X さんの直属の部下であるといいます。

### 制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i < i

### 入力

N
A_2 ... A_N


### 入力例 1

5
1 1 2 2


### 出力例 1

2
2
0
0
0


### 入力例 2

10
1 1 1 1 1 1 1 1 1


### 出力例 2

9
0
0
0
0
0
0
0
0
0


### 入力例 3

7
1 2 3 4 5 6


### 出力例 3

1
1
1
1
1
1
0


Score : 300 points

### Problem Statement

A company has N members, who are assigned ID numbers 1, ..., N.

Every member, except the member numbered 1, has exactly one immediate boss with a smaller ID number.

When a person X is the immediate boss of a person Y, the person Y is said to be an immediate subordinate of the person X.

You are given the information that the immediate boss of the member numbered i is the member numbered A_i. For each member, find how many immediate subordinates it has.

### Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i < i

### Input

Input is given from Standard Input in the following format:

N
A_2 ... A_N


### Output

For each of the members numbered 1, 2, ..., N, print the number of immediate subordinates it has, in its own line.

### Sample Input 1

5
1 1 2 2


### Sample Output 1

2
2
0
0
0


The member numbered 1 has two immediate subordinates: the members numbered 2 and 3.

The member numbered 2 has two immediate subordinates: the members numbered 4 and 5.

The members numbered 3, 4, and 5 do not have immediate subordinates.

### Sample Input 2

10
1 1 1 1 1 1 1 1 1


### Sample Output 2

9
0
0
0
0
0
0
0
0
0


### Sample Input 3

7
1 2 3 4 5 6


### Sample Output 3

1
1
1
1
1
1
0

D - Sum of Large Numbers

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

10^{100}, 10^{100}+1, ..., 10^{100}+NN+1 個の数があります。

この中から K 個以上の数を選ぶとき、その和としてあり得るものの個数を \bmod (10^9+7) で求めてください。

### 制約

• 1 \leq N \leq 2\times 10^5
• 1 \leq K \leq N+1
• 入力は全て整数

### 入力

N K


### 入力例 1

3 2


### 出力例 1

10


• (10^{100})+(10^{100}+1)=2\times 10^{100}+1
• (10^{100})+(10^{100}+2)=2\times 10^{100}+2
• (10^{100})+(10^{100}+3)=(10^{100}+1)+(10^{100}+2)=2\times 10^{100}+3
• (10^{100}+1)+(10^{100}+3)=2\times 10^{100}+4
• (10^{100}+2)+(10^{100}+3)=2\times 10^{100}+5
• (10^{100})+(10^{100}+1)+(10^{100}+2)=3\times 10^{100}+3
• (10^{100})+(10^{100}+1)+(10^{100}+3)=3\times 10^{100}+4
• (10^{100})+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+5
• (10^{100}+1)+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+6
• (10^{100})+(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=4\times 10^{100}+6

### 入力例 2

200000 200001


### 出力例 2

1


### 入力例 3

141421 35623


### 出力例 3

220280457


Score : 400 points

### Problem Statement

We have N+1 integers: 10^{100}, 10^{100}+1, ..., 10^{100}+N.

We will choose K or more of these integers. Find the number of possible values of the sum of the chosen numbers, modulo (10^9+7).

### Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq K \leq N+1
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N K


### Output

Print the number of possible values of the sum, modulo (10^9+7).

### Sample Input 1

3 2


### Sample Output 1

10


The sum can take 10 values, as follows:

• (10^{100})+(10^{100}+1)=2\times 10^{100}+1
• (10^{100})+(10^{100}+2)=2\times 10^{100}+2
• (10^{100})+(10^{100}+3)=(10^{100}+1)+(10^{100}+2)=2\times 10^{100}+3
• (10^{100}+1)+(10^{100}+3)=2\times 10^{100}+4
• (10^{100}+2)+(10^{100}+3)=2\times 10^{100}+5
• (10^{100})+(10^{100}+1)+(10^{100}+2)=3\times 10^{100}+3
• (10^{100})+(10^{100}+1)+(10^{100}+3)=3\times 10^{100}+4
• (10^{100})+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+5
• (10^{100}+1)+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+6
• (10^{100})+(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=4\times 10^{100}+6

### Sample Input 2

200000 200001


### Sample Output 2

1


We must choose all of the integers, so the sum can take just 1 value.

### Sample Input 3

141421 35623


### Sample Output 3

220280457

E - Active Infants

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 人の幼児が左右一列に並んでおり、左から i 番目の幼児の活発度は A_i です。

あなたは一回だけ、幼児たちを好きな順番に並び替えさせることができます。

はじめ左から x 番目に並んでいた幼児が左から y 番目に移動するとき、うれしさが A_x \times |x-y| だけ生じます。

### 制約

• 2 \leq N \leq 2000
• 1 \leq A_i \leq 10^9
• 入力はすべて整数である。

### 入力

N
A_1 A_2 ... A_N


### 入力例 1

4
1 3 4 2


### 出力例 1

20


### 入力例 2

6
5 5 6 1 1 1


### 出力例 2

58


### 入力例 3

6
8 6 9 1 2 1


### 出力例 3

85


Score : 500 points

### Problem Statement

There are N children standing in a line from left to right. The activeness of the i-th child from the left is A_i.

You can rearrange these children just one time in any order you like.

When a child who originally occupies the x-th position from the left in the line moves to the y-th position from the left, that child earns A_x \times |x-y| happiness points.

Find the maximum total happiness points the children can earn.

### Constraints

• 2 \leq N \leq 2000
• 1 \leq A_i \leq 10^9
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N


### Output

Print the maximum total happiness points the children can earn.

### Sample Input 1

4
1 3 4 2


### Sample Output 1

20


If we move the 1-st child from the left to the 3-rd position from the left, the 2-nd child to the 4-th position, the 3-rd child to the 1-st position, and the 4-th child to the 2-nd position, the children earns 1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20 happiness points in total.

### Sample Input 2

6
5 5 6 1 1 1


### Sample Output 2

58


### Sample Input 3

6
8 6 9 1 2 1


### Sample Output 3

85

F - path pass i

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1 から N までの番号がつけられた N 個の頂点を持つ木があります。この木の i 番目の辺は頂点 a_ib_i を結んでいます。 また、各頂点には色が塗られており、 頂点 i に塗られている色は c_i です。ここで、各頂点に塗られている色は 1 以上 N 以下の整数で表されており、同じ整数は同じ色に、異なる整数は異なる色に対応します。

k=1,2,...,N に対して、以下の問題を解いてください。

• k が塗られている頂点を一度以上通るような単純パスの数を求めよ

### 制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq c_i \leq N
• 1 \leq a_i,b_i \leq N
• 与えられるグラフは木である。
• 入力はすべて整数である。

### 入力

N
c_1 c_2 ... c_N
a_1 b_1
:
a_{N-1} b_{N-1}


### 出力

k=1,2,...,N に対する問題の答えを、順番に改行区切りで出力せよ。

### 入力例 1

3
1 2 1
1 2
2 3


### 出力例 1

5
4
0


1 が塗られている頂点を一度以上通る単純パスは、
P_{1,1}\,,\, P_{1,2}\,,\, P_{1,3}\,,\, P_{2,3}\,,\, P_{3,3}
5 つあります。

2 が塗られている頂点を一度以上通る単純パスは、
P_{1,2}\,,\, P_{1,3}\,,\, P_{2,2}\,,\, P_{2,3}
4 つあります。

3 が塗られている頂点を一度以上通る単純パスはありません。

### 入力例 2

1
1


### 出力例 2

1


### 入力例 3

2
1 2
1 2


### 出力例 3

2
2


### 入力例 4

5
1 2 3 4 5
1 2
2 3
3 4
3 5


### 出力例 4

5
8
10
5
5


### 入力例 5

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


### 出力例 5

18
15
0
14
23
0
23
0


Score : 600 points

### Problem Statement

We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i. Additionally, each vertex is painted in a color, and the color of Vertex i is c_i. Here, the color of each vertex is represented by an integer between 1 and N (inclusive). The same integer corresponds to the same color; different integers correspond to different colors.

For each k=1, 2, ..., N, solve the following problem:

• Find the number of simple paths that visit a vertex painted in the color k one or more times.

Note: The simple paths from Vertex u to v and from v to u are not distinguished.

### Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq c_i \leq N
• 1 \leq a_i,b_i \leq N
• The given graph is a tree.
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
c_1 c_2 ... c_N
a_1 b_1
:
a_{N-1} b_{N-1}


### Output

Print the answers for k = 1, 2, ..., N in order, each in its own line.

### Sample Input 1

3
1 2 1
1 2
2 3


### Sample Output 1

5
4
0


Let P_{i,j} denote the simple path connecting Vertex i and j.

There are 5 simple paths that visit a vertex painted in the color 1 one or more times:
P_{1,1}\,,\, P_{1,2}\,,\, P_{1,3}\,,\, P_{2,3}\,,\, P_{3,3}

There are 4 simple paths that visit a vertex painted in the color 2 one or more times:
P_{1,2}\,,\, P_{1,3}\,,\, P_{2,2}\,,\, P_{2,3}

There are no simple paths that visit a vertex painted in the color 3 one or more times.

### Sample Input 2

1
1


### Sample Output 2

1


### Sample Input 3

2
1 2
1 2


### Sample Output 3

2
2


### Sample Input 4

5
1 2 3 4 5
1 2
2 3
3 4
3 5


### Sample Output 4

5
8
10
5
5


### Sample Input 5

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


### Sample Output 5

18
15
0
14
23
0
23
0