{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003e\u003cimg border\u003d\"0\" SRC\u003d\"CDN_BASE_URL/1357f66b507c87a071ec93ad5924bca0?v\u003d1591563500\"\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行,每行两个整数 a, b, 表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。"}},{"title":"Output","value":{"format":"HTML","content":"输出一个整数,表示新建了K 条道路后能达到的最小巡逻距离。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e8 1 \r\n1 2 \r\n3 1 \r\n3 4 \r\n5 3 \r\n7 5 \r\n8 5 \r\n5 6 \u003c/span\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e11\u003c/span\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e10%的数据中,n ≤ 1000, K \u003d 1; \u003cbr\u003e 30%的数据中,K \u003d 1; \u003cbr\u003e 80%的数据中,每个村庄相邻的村庄数不超过 25; \u003cbr\u003e 90%的数据中,每个村庄相邻的村庄数不超过 150; \u003cbr\u003e 100%的数据中,3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。 \u003c/p\u003e"}}]}