P2982 [USACO10FEB] Slowing down G

题目描述

每天，Farmer John 的 N (1 \le N \le 100{,}000) 头奶牛（方便地编号为 $1..N$）都会从牛棚走向各自的私人牧场。牧场形成一棵树，其中牛棚位于牧场 $1$。恰好有 N-1 条无向路径连接这些牧场；直接相连的牧场之间恰好有一条路径。路径 i 连接牧场 A_i 和 B_i $(1 \le A_i \le N, 1 \le B_i \le N)$。

奶牛 i 拥有一个私人牧场 P_i $(1 \le P_i \le N)$。牛棚的小门一次只能让一头奶牛出去，耐心的奶牛们会等待前一头奶牛到达她的私人牧场。首先，奶牛 1 离开并走向牧场 $P_1$。接着奶牛 2 离开并前往牧场 $P_2$，依此类推。

当奶牛 i 走向 P_i 时，她可能会经过已经有奶牛在进食的牧场。当一头奶牛出现在某个牧场时，奶牛 i 在穿过该牧场时会比平时走得更慢，以避免打扰她的朋友。

考虑以下牧场网络，其中括号中的数字表示牧场的主人。

        1 (3)        
       / \
  (1) 4   3 (5)
     / \   
(2) 2   5 (4)

首先，奶牛 1 走向她的牧场：

        1 (3)        
       / \
  [1] 4*  3 (5)
     / \   
(2) 2   5 (4)

当奶牛 2 走向她的牧场时，她首先进入牛棚的牧场，即牧场 1。
然后她绕过牧场 4 中的奶牛 1，最终到达自己的牧场。

        1 (3)
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5 (4)

奶牛 3 根本没走远——她在牛棚的牧场 #1 里闲逛。

        1* [3]
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5 (4)

奶牛 4 在前往牧场 5 的路上，必须在牧场 1 和 4 放慢速度：

        1* [3]
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5* [4]

奶牛 5 因为在牧场 1 遇到奶牛 3 而放慢速度，然后进入自己的私人牧场：

        1* [3]
       / \
  [1] 4*  3*[5]
     / \   
[2] 2*  5* [4]

FJ 想知道每头奶牛需要放慢多少次速度。

输入格式

第 1 行：一个整数 $N$。
第 2..N 行：第 i+1 行包含两个以空格分隔的整数 A_i 和 $B_i$。
第 N+1..N+N 行：第 N+i 行包含一个整数 $P_i$。

输出格式

第 1..N 行：第 i 行包含奶牛 i 需要放慢速度的次数。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

数据范围：$1 \leq A_i, B_i, P_i \leq N \leq 10^5$。

2.4 KiB Raw Permalink Blame History