#P50489. 「NOI2007」 追捕盗贼

「NOI2007」 追捕盗贼

题目描述

魔法国度 Magic Land 里最近出现了一个大盗 Frank ,他在 Magic Land 四处作案,专门窃取政府机关的机密文件(因而有人怀疑 Frank 是敌国派来的间谍)。
为了捉住 Frank,Magic Land 的安全局重拳出击! Magic Land 由 NN 个城市组成,并且这 NN 个城市又由恰好 N1N-1 条公路彼此连接起来,使得任意两个城市间都可以通过若干条公路互达。从数据结构的角度我们也可以说,这 NN 个城市和 N1N-1 条公路形成了一棵树。 例如,下图就是 Magic Land 的一个可能格局( 44 个城市用数字编号, 33 条公路用字母编号):

捕获.JPG

大盗 Frank 能够在公路上以任意速度移动。 比方说,对于上图给出的格局,在 0.000010.00001 秒钟内(或者任意短的一段时间内), Frank 就可以从城市 11 经过城市 22 到达城市 44 ,中间经过了两条公路。

想要生擒 Frank 困难重重,所以安全局派出了经验丰富的警探,这些警探具有非凡的追捕才能:

  • 只要有警探和 Frank 同处一个城市,那么就能够立刻察觉到 Frank,并且将其逮捕。
  • 虽然 Frank 可以在公路上以任意快的速度移动,但是如果有警探和 Frank 在同一条公路上相遇,那么警探也可以立刻察觉到 Frank 并将其逮捕。

安全局完全不知道 Frank 躲在哪个城市,或者正在哪条公路上移动,所以需要制定一个周密的抓捕计划,计划由若干步骤组成。在每一步中,可以做如下几件事中的一个:

  • 在某个城市空降一位警探。警探可以直接从指挥部空降到 Magic Land 的任意一个城市里。此操作记为 L x ,表示在编号为 xx 的城市里空降一位警探。耗时 11 秒。
  • 把留在某个城市里的一位警探直接召回指挥部。以备在以后的步骤中再度空降到某个城市里。此操作记为 B x 。表示把编号为 xx 的城市里的一位警探召回指挥部。耗时 11 秒。
  1. 让待在城市 xx 的一位警探沿着公路移动到城市 yy ,此操作记为 M x y 。耗时 11 秒。当然,前提是城市 xx 和城市 yy 之间有公路。如果在警探移动的过程中,大盗 Frank 也在同一条公路上,那么警探就抓捕到了 Frank 。

现在,由你来制定一套追捕计划,也就是给出若干个步骤,需要保证:无论大盗 Frank 一开始躲在哪儿,也无论 Frank 在整个过程中如何狡猾地移动(Frank 大盗可能会窃取到追捕行动的计划书,所以他一定会想尽办法逃避),他一定会被缉拿归案。 希望参与的警探越少越好,因为经验丰富的警探毕竟不多。

例如对于前面所给的那个图示格局,一个可行的计划如下:

  1. L 2 在城市 22 空降一位警探。注意这一步完成之后,城市 22 里不会有 Frank,否则他将被捉住。
  2. L 2 再在城市 22 空降一位警探。
  3. M 2 1 让城市 22 的一位警探移动到城市 11 。注意城市 22 里还留有另一位警探。这一步完成之后,城市 11 里不会有 Frank ,公路 AA 上也不会有 Frank 。也就是说,假如 Frank 还没有被逮捕,那么他只能是在城市 33 或城市 44 里,或者公路 BB 或公路 CC 上。
  4. B 1 召回城市 11 的一位警探。注意虽然召回了这位警探,但是由于我们始终留了一位警探在城市 22 把守,所以 Frank 仍然不可能跑到城市 11 或者是公路 AA 上。
  5. L 3 在城市 33 空降一位警探。注意这一步可以空降在此之前被召回的那位警探。这一步完成之后,城市 33 里不会有 Frank ,否则他会被捉住。
  6. M 3 2 让城市 33 里的一位警探移动到城市 22 。这一步完成之后,如果 Frank 还没有被捉住,那他只能是在公路 CC 上或者城市 44 里。注意这一步之后,城市 22 里有两位警探。
  7. M 2 4 让城市 22 里的一位警探移动到城市 44 。这一步完成之后,Frank 一定会被捉住,除非他根本就没来 Magic Land 。 这个计划总共需要 22 位警探的参与。可以证明:如果自始至终只有 11 名或者更少的警探参与,则 Frank 就会逍遥法外。

你的任务很简单:对于一个输入的 Magic Land 的格局,计算 SS ,也就是为了追捕 Frank 至少需要投入多少位警探,并且给出相应的追捕计划步骤。

输入格式

输入给出了 Magic Land 的格局。
第一行一个整数 NN,代表有 NN 个城市,城市的编号是 1,2,,N1 , 2 , \dots , N
接下来 N1N-1 行,每行有两个用空格分开的整数 xi,yix_i , y_i,代表城市 xi,yix_i , y_i 之间有公路相连。保证 1xi,yiN1 \leqslant x_i , y_ i \leqslant N

输出格式

输出你所给出的追捕计划。 第一行请输出一个整数 SS ,代表追捕计划需要多少位警探。
第二行请输出一个整数 TT ,代表追捕计划总共有多少步。
接下来请输出 TT 行,依次描述了追捕计划的每一步。每行必须是以下三种形式之一:

  • L x,其中 L 是大写字母,接着是一个空格,再接着是整数 xx ,代表在城市 xx 空降一位警探。你必须保证 1xN1 \le x \le N
  • B x,其中 B 是大写字母,接着是一个空格,再接着是整数 xx ,代表召回城市 xx 的一位警探。你必须保证 1xN1 \le x \le N ,且你的计划执行到这一步之前,城市 xx 里面确实至少有一位警探。
  • M x y ,其中 M 是大写字母,接着是一个空格,再接着是整数 xx ,再跟一个空格,最后一个是整数 yy 。代表让城市 xx 的一位警探沿着公路移动到城市 yy 。你必须保证 1x,yN1 \le x , y \le N ,且你的计划执行到这一步之前,城市 xx 里面确实至少有一位警探,且城市 x,yx , y 之前确实有公路。 必须保证输出的 SS 确实等于追捕计划中所需要的警探数目。

样例

4
1 2
3 2
2 4
2
7
L 2
L 2
M 2 1
B 1
L 3
M 3 2
M 2 4

数据范围与提示

数据规模和约定

输入保证描述了一棵连通的 NN 结点树, 1N10001 \le N \le 1000

评分标准

对于任何一个测试点: 如果输出的追捕计划不合法,或者整个追捕计划的步骤数 TT 超过了 2000020000 ,或者追捕计划结束之后,不能保证捉住 Frank ,则不能得分。 否则,用你输出的 SS 和我们已知的标准答案 SS^* 相比较:

  1. S<SS < S^* ,则得到 100%100\% 的分。(原题为 120%120\% ,此处鉴于技术性原因更改。)
  2. S=SS = S^* ,则得到 100%100\% 的分。
  3. S<SS+2S^* < S \le S^*+2 ,则得到 60%60\% 的分。
  4. S+2<SS+4S^*+2 < S \le S^*+4 ,则得到 40%40\% 的分。
  5. S+4<SS+8S^*+4 < S \le S^*+8 ,则得到 20%20\% 的分。
  6. S>S+8S > S^*+8,则得到 10%10\% 的分。