【正文】
tional. Output it as an irreducible fraction. On the first line of the output file print the numerator of the winning probability. On the second line print its denominator. Both numerator and denominator must be printed without leading zeroes. Remember that the fraction must be irreducible. Sample Input output 2 4 6 1 3 Source Northeastern Europe 2022, Northern Subregion 例三的原題:追捕盜賊 問題描述 魔法國度 Magic Land 里最近出現(xiàn)了一個大盜 Frank,他在 Magic Land 四處作案,專門竊取政府機關(guān)的機密文件(因而有人懷疑 Frank 是敵國派來的間諜)。 為了捉住 Frank, Magic Land 的安全局重拳出擊! Magic Land 由 N 個城市組成,并且這 N 個城市又由恰好 N1 條公路彼此連接起來,使得任意兩個城市間都可以通過若干條公路互達。從數(shù)據(jù)結(jié)構(gòu)的角度我 們也可以說,這 N 個城市和 N1 條公路形成了一棵樹。 例如,下圖就是 Magic Land 的一個可能格局( 4 個城市用數(shù)字編號, 3 條公路用字母編號): 大盜 Frank 能夠在公路上以任意速度移動。 比方說,對于上圖給出的格局,在 秒鐘內(nèi)(或者任意短的一段時間 內(nèi)), Frank 就可以從城市 1 經(jīng)過城市 2 到達城市 4,中間經(jīng)過了兩條公路。 想要生擒 Frank 困難重重,所以安全局派出了經(jīng)驗豐富的警探,這些警探具有非凡的追捕才能: Frank 同處一個城市,那么就能夠立刻察覺到 Frank,并且將其逮捕。 Frank 可以在公路上以任意快的速度移動,但是如果有警探和 Frank 在同一條公路上相遇,那么警探也可以立刻察覺到 Frank并將其逮捕。 安全局完全不知道 Frank躲在哪個城市,或者正在哪條公路上移動,所以需要制定一個周密的抓捕計劃,計劃由若干步驟組成。在每一步中,可以做如下幾件事中的一個: 。警探可以直接從指揮部空降到 Magic Land的任 意一個城市里。此操作記為“ L x”,表示在編號為 x的城市里空降一位警探。耗時 1秒。 。以備在以后的步驟中再度空降到某個城市里。此操作記為“ B x”。表示把編號為 x 的城市里的一位警探召回指揮部。耗時 1秒。 x 的一位警探沿著公路移動到城市 y,此操作記為“ M x y”。耗時 1 秒。當然,前提是城市 x 和城市 y 之間有公路。如果在警探移動的過程中,大盜 Frank 也在同一條公路上,那么警探就抓捕到了 Frank。 現(xiàn)在,由你來制定一套追捕計劃,也就是給出若干個步驟,需要保證:無論大盜 Frank一開始躲在哪兒,也無論 Frank 在整個過程中如何狡猾地移動( Frank大盜可能會竊取到追捕行動的計劃書,所以他一定會想盡辦法逃避),他一定會被緝拿歸案。 希望參與的警探越少越好,因為經(jīng)驗豐富的警探畢竟不多。 例如對于前面所給的那個圖示格局,一個可行的計劃如下: 1. L 2 在城市 2 空降一位警探。注意這一步完成之后,城市 2里不會有 Frank,否則他將被捉住。 2. L 2 再在城市 2 空降一位警探。 3. M 2 1 讓城市 2 的一位警探移動到城市 1。注意城市 2 里還留有另一位警探。這一步完成之后,城市 1 里不會有 Frank,公路 A 上也不會有 Frank。也就是說,假如 Frank 還沒有被逮捕,那么他只能是在城市 3 或城市 4 里,或者公路 B 或公路 C 上。 4. B 1 召 回城市 1 的一位警探。注意雖然召回了這位警探,但是由于我們始終留了一位警探在城市 2 把守,所以 Frank 仍然不可能跑到城市 1 或者是公路A 上。 5. L 3 在城市 3 空降一位警探。注意這一步可以空降在此之前被召回的那位警探。這一步完成之后,城市 3 里不會有 Frank,否則他會被捉住。 6. M 3 2 讓城市 3 里的一位警探移動到城市 2。這一步完成之后,如果 Frank 還沒有被捉住,那他只能是在公路 C 上或者城市 4 里。注意這一步之后,城市 2 里有兩位警探。 7. M 2 4 讓城市 2 里的一位警探移動到城市 4。這一步完成之后, Frank 一定會被捉住,除非他根本就沒來 Magic Land。 這個計劃總共需要 2 位警探的參與??梢宰C明:如果自始至終只有 1 名或者 更少的警探參與,則 Frank 就會逍遙法外。 你的任務(wù)很簡單:對于一個輸入的 Magic Land 的格局,計算 S,也就是為了 追捕 Frank 至少需要投入多少位警探,并且給出相應(yīng)的追捕計劃步驟。 輸入文件 輸入文件給出了 Magic Land 的格局。 第一行一個整數(shù) N,代表有 N 個城市,城 市的編號是 1~N。 接下來 N1 行,每行有兩個用空格分開的整數(shù) xi, yi,代表城市 xi, yi 之間有公路相連。保證 1≤ xi,yi≤ N。 輸出文件 向輸出文件輸出你所給出的追捕計劃。 第一行請輸出一個整數(shù) S,代表追捕計劃需要多少位警探。 第二行請輸出一個整數(shù) T,代表追捕計劃總共有多少步。 接下來請輸出 T 行,依次描述了追捕計劃的每一步。每行必須是以下三種形式之一: “ L x”,其中 L 是大寫字母,接著是一個空格,再接著是整數(shù) x,代表在城市 x 空降一位警探。你必須保證 1≤ x≤ N。 “ B x”,其中 B 是大寫字母,接著是一個空格,再接著是整數(shù) x,代表召回城市 x 的一位警探。你必須保證 1≤ x≤ N,且你的計劃執(zhí)行到這一步之前,城市 x 里面確實至少有一位警探。 “ M x y”,其中 M 是大寫字母,接著是一個空格,再接著是整數(shù) x,再跟一個空格,最后一個是整數(shù) y。代表讓城市 x 的一位警探沿著公路移動到城市 y。你必須保證 1≤ x, y≤ N,且你的計劃執(zhí)行到這一步之前,城市 x 里面確實至少有一位警探,且城市 x, y 之前確實有公路。 必須保證輸出的 S 確實等于追捕計劃中所需要的警探數(shù)目。 樣例輸入 樣例輸出 4 2 1 2 3 2 2 4 7 L 2 L 2 M 2 1 B 1 L 3 M 3 2 M 2 4 評分標準 對于任何一個測試點: 如果輸出的追捕計劃不合法,或者整個追捕計劃的步驟數(shù) T 超過了 20220, 或者追捕計劃結(jié)束之后,不能保證捉住 Frank,則不能得分。 否則,用你輸出的 S 和我們已知的標準答案 S*相比較: 1. 若 SS*,則得到 120%的分。 2. 若 S=S*,則得到 100%的分。 3. 若 S*S≤ S*+2,則得到 60%的分。 4. 若 S*+2S≤ S*+4,則得到 40%的分。 5. 若 S*+4S≤ S*+8,則得到 20%的分。 6. 若 SS*+8,則得到 10%的分。 數(shù)據(jù)規(guī)模和約定 輸入保證描述了一棵連通的 N 結(jié)點樹, 1≤ N≤ 1 000。 例題五原題: PKU3237 tree Description You are given a tree with N nodes. The tree39。s nodes are numbered 1 through N and its edges are numbered 1 through N ? 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms: CHANGE i v Change the weight of the ith edge to v NEGATE a b Negate the weight of every edge on the path from a to b QUERY a b Find the maximum weight of edges on the path from a to b Input The input contains multiple test cases. The first line of input contains an integer t (t=20), the number of test cases. Then follow the test cases. Each test case is preceded by an empty line. The first nonempty line of its contains N (N = 10,000). The next N ? 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word DONE ends the test case. Output For each QUERY instruction, output the result on a separate line. Sample Input 1 3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE Sample Output 1 3 Source POJ , Lei, Tao