No.3309 Aging Railway
タグ : / 解いたユーザー数 44
作問者 :
yu23578
/ テスター :
👑 
p-adic
注意
この問題の実行時間制限は3000msです。
問題文
yu23578王国内を走っているY鉄道には $N$ 個の駅があり、 $1$ から $N$ までの番号が付けられています。
また、Y鉄道には $N-1$ 本の線路があり、 $1$ から $N-1$ までの番号が付けられています。線路 $i (1 \le i \le N-1)$ は駅 $u_i$ と駅 $v_i$ を双方向に結んでいて、その上を電車が走っています。
そして、 $M$ 人のサラリーマンがY鉄道を利用しており、 $j (1 \le j \le M)$ 人目のサラリーマンは自宅の最寄り駅 $s_j$ から会社の最寄駅 $t_j$ まで通勤しています。
しかし、Y鉄道は老朽化が進んでいるため、現在から $k (1 \le k \le N-1)$ 年後に線路 $k$ が廃線となることが分かっており、廃線となった線路は使えなくなります。
このとき、各 $k = 1,2,3,\cdots ,N-1$ に対して、以下の問題に対する答えを求めてください $:$
・ $k+0.5$ 年後に自宅の最寄駅から会社の最寄駅までY鉄道で通勤することができるサラリーマンは何人いますか？
制約
・$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$
・現在、どの駅からどの駅へもいくつかの線路を経由して移動できる。
・入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。$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$
出力
$N-1$ 行出力してください。 $k (1 \le k \le N-1)$ 行目には、$k+0.5$ 年後に自宅の最寄駅から会社の最寄駅までY鉄道で通勤することができるサラリーマンの人数を解答してください。
サンプル
サンプル1
入力
3 2
1 2
1 3
1 3
2 3
出力
1
0
$1+0.5$ 年後、線路 $1$ のみ使用不可になります。このとき、サラリーマン $1$ は駅 $1$ から駅 $3$ まで通勤できますが、サラリーマン $2$ は駅 $2$ から駅 $3$ まで通勤できません。
よって $1$ 行目には $1$ を出力してください。
$2+0.5$ 年後、線路 $1$ と線路 $2$ が使用不可になります。このとき、サラリーマン $1$ もサラリーマン $2$ も通勤できません。
よって $2$ 行目には $0$ を出力してください。
サンプル2
入力
2 3
1 2
1 2
1 2
1 2
出力
0
同じ経路で通勤するサラリーマンがいる可能性もあります。
サンプル3
入力
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
出力
4 3 3 1 1 0 0 0 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。