{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003ch3\u003e问题描述\u003c/h3\u003e\n\n\u003cp\u003e\n农夫约翰有N个荒芜的牧场(2 \u003c\u003d N \u003c\u003d 100,000),这些牧场通过N-1条双向道路相连,使得任意两个牧场之间都恰好有一条路径。爱吃草的奶牛贝西经常抱怨说牧场之间的道路上没有草。约翰农夫非常爱贝西,今天他终于要在道路上种草了。他将使用一个包含M个步骤的过程(1 \u003c\u003d M \u003c\u003d 100,000)。\n\u003c/p\u003e\n\n\u003cp\u003e在每一步中会发生以下两件事中的一件:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e约翰农夫会选择两个牧场,并沿着这两个牧场之间的每条道路种一片草,或者,\u003c/li\u003e\n \u003cli\u003e贝西会询问某条道路上有多少片草,约翰农夫必须回答她的问题。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e约翰农夫数数很差 —— 帮助他回答贝西的问题!\u003c/p\u003e\n\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cp\u003e* 第1行: 两个用空格分隔的整数 N 和 M\u003c/p\u003e\n\u003cp\u003e* 第2行至第N行: 每行两个用空格分隔的整数,描述一条道路的端点。\u003c/p\u003e\n\u003cp\u003e* 第N+1行至第N+M行: 第i+1行描述第i步。行的第一个字符是P或Q,描述约翰农夫是在种草还是在查询。接下来是两个用空格分隔的整数 A_i 和 B_i (1 \u003c\u003d A_i, B_i \u003c\u003d N),描述约翰农夫的行动或查询。\u003c/p\u003e\n\n\u003ch3\u003e输出\u003c/h3\u003e\n\u003cp\u003e* 第1行至第???行: 每行包含一个查询的答案,按照查询在输入中出现的顺序排列。\u003c/p\u003e\n\n\u003ch3\u003e示例\u003c/h3\u003e\n\u003ch4\u003e示例输入\u003c/h4\u003e\n\u003cpre\u003e4 6\r\n1 4\r\n2 4\r\n3 4\r\nP 2 3\r\nP 1 3\r\nQ 3 4\r\nP 1 4\r\nQ 2 4\r\nQ 1 4\u003c/pre\u003e\n\n\u003ch4\u003e示例输出\u003c/h4\u003e\n\u003cpre\u003e2\r\n1\r\n2\u003c/pre\u003e\n\n\u003cp\u003e\u003cb\u003e[ Edited by EB ]\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e警告:\u003c/b\u003e 一些输入文件已损坏。\u003c/p\u003e\n\u003c/div\u003e"}}]}