{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cbr\u003e\nBob喜欢玩电脑游戏,尤其是策略游戏,但有时他找不到解决方案,会变得很难过。现在他面临以下问题。他必须保卫一座中世纪城市,其道路形成一棵树。Bob需要放置尽可能少的士兵,保卫树上所有的边。士兵只能放在节点上,但是却可以保卫所有与这个节点相邻的边。\n你的程序应该找到Bob必须放置的最少数量的士兵。\n\u003cbr\u003e\n例如,对于以下树:\n\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/43f52b994a402a64db401be44050adc4?v\u003d1682324259\"\u003e\u003c/center\u003e\n\u003cbr\u003e解决方案是一个士兵(在节点1处)。"}},{"title":"Input","value":{"format":"HTML","content":"输入以文本格式包含多个数据集。每个数据集表示一棵树,具有以下描述:\n\u003cbr\u003e\u003cul\u003e\n\u003cbr\u003e\u003cli\u003e节点数\n\u003cbr\u003e\u003c/li\u003e\u003cli\u003e每个节点的描述如下格式:\n\u003cbr\u003e节点标识符:(道路数)节点标识符\u003csub\u003e1\u003c/sub\u003e 节点标识符\u003csub\u003e2\u003c/sub\u003e ... 节点标识符 \u003csub\u003enumber_of_roads\u003c/sub\u003e\n\u003cbr\u003e或者\n\u003cbr\u003e节点标识符:(0)\n\u003cbr\u003e\u003c/li\u003e\u003c/ul\u003e\n\u003cbr\u003e节点标识符是0到n-1之间的整数,对于n个节点(0 \u003c n \u003c\u003d 1500),每行输入的number_of_roads不超过10。输入数据中的每条边仅出现一次。"}},{"title":"Output","value":{"format":"HTML","content":"输出应打印在标准输出上。对于每个给定的输入数据集,在单行中打印一个整数,给出结果(最少的士兵数)。下面是一个例子:"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0:(1) 1\n1:(2) 2 3\n2:(0)\n3:(0)\n5\n3:(3) 1 4 2\n1:(1) 0\n2:(0)\n0:(0)\n4:(0)\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}