問題一覧 > 通常問題

No.3309 Aging Railway

レベル : / AI推定難易度 : 1150 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 54
作問者 : yu23578 / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 12692 / 自分の提出
問題文最終更新日: 2025-10-24 21:34:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 486 オムニバス (順位表) の他の問題:

Note

The time limit for this problem is 3000ms.

Problem Statement

Railway Y, which runs in the Kingdom of yu23578, has $N$ stations, numbered from $1$ to $N$.

Railway Y also has $N-1$ tracks, numbered from $1$ to $N-1$. Track $i (1 \le i \le N-1)$ connects station $u_i$ and station $v_i$ bidirectionally, and trains run on it.

There are $M$ office workers using Railway Y, and the $j (1 \le j \le M)$-th office worker commutes from station $s_j$, the nearest station to their home, to station $t_j$, the nearest station to their company.

However, because Railway Y is aging, it is known that track $k$ will be abolished $k (1 \le k \le N-1)$ years from now, and an abolished track can no longer be used.

For each $k = 1,2,3,\cdots ,N-1$, find the answer to the following question $:$
 ・ How many office workers can commute by Railway Y from the nearest station to their home to the nearest station to their company $k+0.5$ years from now?

Constraints

・$2 \le N \le 3000$
・$1 \le M \le 5 \times 10^5$
・$1 \le u_i < v_i \le N$
・$1 \le s_j < t_j \le N$
・At present, it is possible to travel from any station to any station via some tracks.
・All inputs are integers.

Input

The input is given from standard input in the following format.
$N\ M$
$u_1\ v_1$
$u_2\ v_2$
$u_3\ v_3$
$\vdots$
$u_{N-1}\ v_{N-1}$
$s_1\ t_1$
$s_2\ t_2$
$s_3\ t_3$
$\vdots$
$s_M\ t_M$

Output

Print $N-1$ lines. On the $k (1 \le k \le N-1)$-th line, print the number of office workers who can commute by Railway Y from the nearest station to their home to the nearest station to their company $k+0.5$ years from now.

Sample

Sample 1
Input
3 2
1 2
1 3
1 3
2 3
Output
1
0

After $1+0.5$ years, only track $1$ is unusable. At this time, office worker $1$ can commute from station $1$ to station $3$, but office worker $2$ cannot commute from station $2$ to station $3$.
Therefore, print $1$ on line $1$.

After $2+0.5$ years, track $1$ and track $2$ are unusable. At this time, neither office worker $1$ nor office worker $2$ can commute.
Therefore, print $0$ on line $2$.

Sample 2
Input
2 3
1 2
1 2
1 2
1 2
Output
0

There may be office workers who commute along the same route.

Sample 3
Input
10 4
2 3
2 6
1 8
1 4
6 10
5 6
1 9
1 6
7 9
1 4
4 6
1 5
2 5
Output
4
3
3
1
1
0
0
0
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。