【正文】 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)了一個(gè)大盜 Frank，他在 Magic Land 四處作案，專門竊取政府機(jī)關(guān)的機(jī)密文件（因而有人懷疑 Frank 是敵國派來的間諜）。 為了捉住 Frank， Magic Land 的安全局重拳出擊！ Magic Land 由 N 個(gè)城市組成，并且這 N 個(gè)城市又由恰好 N1 條公路彼此連接起來，使得任意兩個(gè)城市間都可以通過若干條公路互達(dá)。從數(shù)據(jù)結(jié)構(gòu)的角度我 們也可以說，這 N 個(gè)城市和 N1 條公路形成了一棵樹。 例如，下圖就是 Magic Land 的一個(gè)可能格局（ 4 個(gè)城市用數(shù)字編號(hào)， 3 條公路用字母編號(hào)）： 大盜 Frank 能夠在公路上以任意速度移動(dòng)。 比方說，對于上圖給出的格局，在 秒鐘內(nèi)（或者任意短的一段時(shí)間 內(nèi)）， Frank 就可以從城市 1 經(jīng)過城市 2 到達(dá)城市 4，中間經(jīng)過了兩條公路。 想要生擒 Frank 困難重重，所以安全局派出了經(jīng)驗(yàn)豐富的警探，這些警探具有非凡的追捕才能： Frank 同處一個(gè)城市，那么就能夠立刻察覺到 Frank，并且將其逮捕。 Frank 可以在公路上以任意快的速度移動(dòng)，但是如果有警探和 Frank 在同一條公路上相遇，那么警探也可以立刻察覺到 Frank并將其逮捕。 安全局完全不知道 Frank躲在哪個(gè)城市，或者正在哪條公路上移動(dòng)，所以需要制定一個(gè)周密的抓捕計(jì)劃，計(jì)劃由若干步驟組成。在每一步中，可以做如下幾件事中的一個(gè)： 。警探可以直接從指揮部空降到 Magic Land的任 意一個(gè)城市里。此操作記為“ L x”，表示在編號(hào)為 x的城市里空降一位警探。耗時(shí) 1秒。 。以備在以后的步驟中再度空降到某個(gè)城市里。此操作記為“ B x”。表示把編號(hào)為 x 的城市里的一位警探召回指揮部。耗時(shí) 1秒。 x 的一位警探沿著公路移動(dòng)到城市 y，此操作記為“ M x y”。耗時(shí) 1 秒。當(dāng)然，前提是城市 x 和城市 y 之間有公路。如果在警探移動(dòng)的過程中，大盜 Frank 也在同一條公路上，那么警探就抓捕到了 Frank。 現(xiàn)在，由你來制定一套追捕計(jì)劃，也就是給出若干個(gè)步驟，需要保證：無論大盜 Frank一開始躲在哪兒，也無論 Frank 在整個(gè)過程中如何狡猾地移動(dòng)（ Frank大盜可能會(huì)竊取到追捕行動(dòng)的計(jì)劃書，所以他一定會(huì)想盡辦法逃避），他一定會(huì)被緝拿歸案。 希望參與的警探越少越好，因?yàn)榻?jīng)驗(yàn)豐富的警探畢竟不多。 例如對于前面所給的那個(gè)圖示格局，一個(gè)可行的計(jì)劃如下： 1. L 2 在城市 2 空降一位警探。注意這一步完成之后，城市 2里不會(huì)有 Frank，否則他將被捉住。 2. L 2 再在城市 2 空降一位警探。 3. M 2 1 讓城市 2 的一位警探移動(dòng)到城市 1。注意城市 2 里還留有另一位警探。這一步完成之后，城市 1 里不會(huì)有 Frank，公路 A 上也不會(huì)有 Frank。也就是說，假如 Frank 還沒有被逮捕，那么他只能是在城市 3 或城市 4 里，或者公路 B 或公路 C 上。 4. B 1 召 回城市 1 的一位警探。注意雖然召回了這位警探，但是由于我們始終留了一位警探在城市 2 把守，所以 Frank 仍然不可能跑到城市 1 或者是公路A 上。 5. L 3 在城市 3 空降一位警探。注意這一步可以空降在此之前被召回的那位警探。這一步完成之后，城市 3 里不會(huì)有 Frank，否則他會(huì)被捉住。 6. M 3 2 讓城市 3 里的一位警探移動(dòng)到城市 2。這一步完成之后，如果 Frank 還沒有被捉住，那他只能是在公路 C 上或者城市 4 里。注意這一步之后，城市 2 里有兩位警探。 7. M 2 4 讓城市 2 里的一位警探移動(dòng)到城市 4。這一步完成之后， Frank 一定會(huì)被捉住，除非他根本就沒來 Magic Land。 這個(gè)計(jì)劃總共需要 2 位警探的參與?？梢宰C明：如果自始至終只有 1 名或者 更少的警探參與，則 Frank 就會(huì)逍遙法外。 你的任務(wù)很簡單：對于一個(gè)輸入的 Magic Land 的格局，計(jì)算 S，也就是為了 追捕 Frank 至少需要投入多少位警探，并且給出相應(yīng)的追捕計(jì)劃步驟。 輸入文件 輸入文件給出了 Magic Land 的格局。 第一行一個(gè)整數(shù) N，代表有 N 個(gè)城市，城 市的編號(hào)是 1~N。 接下來 N1 行，每行有兩個(gè)用空格分開的整數(shù) xi， yi，代表城市 xi， yi 之間有公路相連。保證 1≤ xi,yi≤ N。 輸出文件 向輸出文件輸出你所給出的追捕計(jì)劃。 第一行請輸出一個(gè)整數(shù) S，代表追捕計(jì)劃需要多少位警探。 第二行請輸出一個(gè)整數(shù) T，代表追捕計(jì)劃總共有多少步。 接下來請輸出 T 行，依次描述了追捕計(jì)劃的每一步。每行必須是以下三種形式之一： “ L x”，其中 L 是大寫字母，接著是一個(gè)空格，再接著是整數(shù) x，代表在城市 x 空降一位警探。你必須保證 1≤ x≤ N。 “ B x”，其中 B 是大寫字母，接著是一個(gè)空格，再接著是整數(shù) x，代表召回城市 x 的一位警探。你必須保證 1≤ x≤ N，且你的計(jì)劃執(zhí)行到這一步之前，城市 x 里面確實(shí)至少有一位警探。 “ M x y”，其中 M 是大寫字母，接著是一個(gè)空格，再接著是整數(shù) x，再跟一個(gè)空格，最后一個(gè)是整數(shù) y。代表讓城市 x 的一位警探沿著公路移動(dòng)到城市 y。你必須保證 1≤ x, y≤ N，且你的計(jì)劃執(zhí)行到這一步之前，城市 x 里面確實(shí)至少有一位警探，且城市 x, y 之前確實(shí)有公路。 必須保證輸出的 S 確實(shí)等于追捕計(jì)劃中所需要的警探數(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 評分標(biāo)準(zhǔn) 對于任何一個(gè)測試點(diǎn)： 如果輸出的追捕計(jì)劃不合法，或者整個(gè)追捕計(jì)劃的步驟數(shù) T 超過了 20220， 或者追捕計(jì)劃結(jié)束之后，不能保證捉住 Frank，則不能得分。 否則，用你輸出的 S 和我們已知的標(biāo)準(zhǔn)答案 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é)點(diǎn)樹， 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