{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cdiv style\u003d\"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-family: \u0027Helvetica Neue\u0027, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px; \"\u003e\r\n\t\u003cp style\u003d\"margin-top: 1.5em; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 1em; line-height: 1.5em; \"\u003e\r\n\t\tA\u0026nbsp;\u003cspan class\u003d\"tex-font-style-it\" style\u003d\"font-style: italic; \"\u003etree\u003c/span\u003e\u0026nbsp;is a connected graph that doesn\u0026#39;t contain any cycles.\u003c/p\u003e\r\n\t\u003cp style\u003d\"margin-top: 1.5em; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 1em; line-height: 1.5em; \"\u003e\r\n\t\tThe\u0026nbsp;\u003cspan class\u003d\"tex-font-style-it\" style\u003d\"font-style: italic; \"\u003edistance\u003c/span\u003e\u0026nbsp;between two vertices of a tree is the length (in edges) of the shortest path between these vertices.\u003c/p\u003e\r\n\t\u003cp style\u003d\"margin-top: 1.5em; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 1em; line-height: 1.5em; \"\u003e\r\n\t\tYou are given a tree with\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e\u0026nbsp;vertices and a positive number\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e. Find the number of distinct pairs of the vertices which have a distance of exactly\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e\u0026nbsp;between them. Note that pairs (\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e,\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e) and (\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e,\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e) are considered to be the same pair.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"input-specification\" style\u003d\"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-family: \u0027Helvetica Neue\u0027, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px; \"\u003e\r\n\t\u003cdiv class\u003d\"section-title\" style\u003d\"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 16px; font-weight: bold; \"\u003e\r\n\t\tInput\u003c/div\u003e\r\n\t\u003cp style\u003d\"margin-top: 1.5em; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 1em; line-height: 1.5em; \"\u003e\r\n\t\tThe first line contains two integers\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e\u0026nbsp;and\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e\u0026nbsp;(\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e1\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003en\u003c/i\u003e\u0026thinsp;\u0026le;\u0026thinsp;50000\u003c/span\u003e,\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e1\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003ek\u003c/i\u003e\u0026thinsp;\u0026le;\u0026thinsp;500\u003c/span\u003e) \u0026mdash; the number of vertices and the required distance between the vertices.\u003c/p\u003e\r\n\t\u003cp style\u003d\"margin-top: 1.5em; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 1em; line-height: 1.5em; \"\u003e\r\n\t\tNext\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003en\u003c/i\u003e\u0026thinsp;-\u0026thinsp;1\u003c/span\u003e\u0026nbsp;lines describe the edges as \u0026quot;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003cspan data-scayt_word\u003d\"ai\" data-scaytid\u003d\"8\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\" style\u003d\"font-size: 13px; line-height: 0; position: relative; vertical-align: baseline; bottom: -0.25em; \"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\u003c/span\u003e\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\" style\u003d\"font-size: 13px; line-height: 0; position: relative; vertical-align: baseline; bottom: -0.25em; \"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\u0026quot; (without the quotes) (\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e1\u0026thinsp;\u0026le;\u0026thinsp;\u003cspan data-scayt_word\u003d\"ai\" data-scaytid\u003d\"9\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\" style\u003d\"font-size: 13px; line-height: 0; position: relative; vertical-align: baseline; bottom: -0.25em; \"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e,\u0026thinsp;\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\" style\u003d\"font-size: 13px; line-height: 0; position: relative; vertical-align: baseline; bottom: -0.25em; \"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003en\u003c/i\u003e\u003c/span\u003e,\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003cspan data-scayt_word\u003d\"ai\" data-scaytid\u003d\"10\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\" style\u003d\"font-size: 13px; line-height: 0; position: relative; vertical-align: baseline; bottom: -0.25em; \"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\u0026thinsp;\u0026ne;\u0026thinsp;\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\" style\u003d\"font-size: 13px; line-height: 0; position: relative; vertical-align: baseline; bottom: -0.25em; \"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e), where\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003cspan data-scayt_word\u003d\"ai\" data-scaytid\u003d\"11\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\" style\u003d\"font-size: 13px; line-height: 0; position: relative; vertical-align: baseline; bottom: -0.25em; \"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\u003c/span\u003e\u0026nbsp;and\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\" style\u003d\"font-size: 13px; line-height: 0; position: relative; vertical-align: baseline; bottom: -0.25em; \"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\u0026nbsp;are the vertices connected by the\u0026nbsp;\u003cspan data-scayt_word\u003d\"i-th\" data-scaytid\u003d\"14\"\u003e\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th\u003c/span\u003e edge. All given edges are different.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"output-specification\" style\u003d\"margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-family: \u0027Helvetica Neue\u0027, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px; \"\u003e\r\n\t\u003cdiv class\u003d\"section-title\" style\u003d\"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 16px; font-weight: bold; \"\u003e\r\n\t\tOutput\u003c/div\u003e\r\n\t\u003cp style\u003d\"margin-top: 1.5em; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 1em; line-height: 1.5em; \"\u003e\r\n\t\tPrint a single integer \u0026mdash; the number of distinct pairs of the tree\u0026#39;s vertices which have a distance of exactly\u0026nbsp;\u003cspan class\u003d\"tex-span\" style\u003d\"font-size: 18px; font-family: \u0027times new roman\u0027, sans-serif; \"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e\u0026nbsp;between them.\u003c/p\u003e\r\n\t\u003cp style\u003d\"margin-top: 1.5em; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 1em; line-height: 1.5em; \"\u003e\r\n\t\tPlease do not use the\u0026nbsp;\u003cspan class\u003d\"tex-font-style-tt\" style\u003d\"font-size: 15px; font-family: \u0027courier new\u0027, monospace; \"\u003e%\u003cspan data-scayt_word\u003d\"lld\" data-scaytid\u003d\"15\"\u003elld\u003c/span\u003e\u003c/span\u003e\u0026nbsp;specifier to read or write 64-bit integers in ะก++. It is preferred to use the\u0026nbsp;\u003cspan class\u003d\"tex-font-style-tt\" style\u003d\"font-size: 15px; font-family: \u0027courier new\u0027, monospace; \"\u003e\u003cspan data-scayt_word\u003d\"cin\" data-scaytid\u003d\"16\"\u003ecin\u003c/span\u003e\u003c/span\u003e,\u0026nbsp;\u003cspan class\u003d\"tex-font-style-tt\" style\u003d\"font-size: 15px; font-family: \u0027courier new\u0027, monospace; \"\u003e\u003cspan data-scayt_word\u003d\"cout\" data-scaytid\u003d\"17\"\u003ecout\u003c/span\u003e\u003c/span\u003e\u0026nbsp;streams or the\u0026nbsp;\u003cspan class\u003d\"tex-font-style-tt\" style\u003d\"font-size: 15px; font-family: \u0027courier new\u0027, monospace; \"\u003e%\u003c/span\u003e\u003cspan data-scayt_word\u003d\"I64dspecifier\" data-scaytid\u003d\"18\"\u003e\u003cspan class\u003d\"tex-font-style-tt\" style\u003d\"font-size: 15px; font-family: \u0027courier new\u0027, monospace; \"\u003eI64d\u003c/span\u003especifier\u003c/span\u003e.\u003c/p\u003e\r\n\u003c/div\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e\r\n.input, .output {border: \u003cspan data-scaytid\u003d\"1\" data-scayt_word\u003d\"1px\"\u003e1px\u003c/span\u003e solid #888888;} .output {margin-bottom:\u003cspan data-scaytid\u003d\"3\" data-scayt_word\u003d\"1em\"\u003e1em\u003c/span\u003e;position:relative;top:\u003cspan data-scaytid\u003d\"4\" data-scayt_word\u003d\"-1px\"\u003e-1px\u003c/span\u003e;} .output pre,.input pre {background-color:#\u003cspan data-scaytid\u003d\"5\" data-scayt_word\u003d\"EFEFEF\"\u003eEFEFEF\u003c/span\u003e;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#\u003cspan data-scaytid\u003d\"6\" data-scayt_word\u003d\"FFFFFF\"\u003eFFFFFF\u003c/span\u003e;border-bottom: \u003cspan data-scaytid\u003d\"2\" data-scayt_word\u003d\"1px\"\u003e1px\u003c/span\u003e solid #888888;font-family:\u003cspan data-scaytid\u003d\"7\" data-scayt_word\u003d\"arial\"\u003earial\u003c/span\u003e;font-weight:bold;padding:0.25em;}\u003c/style\u003e\r\n\u003cdiv class\u003d\"input\"\u003e\r\n\t\u003cp\u003e\r\n\t\tInput\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t5 2\u003cbr /\u003e\r\n\t\t1 2\u003cbr /\u003e\r\n\t\t2 3\u003cbr /\u003e\r\n\t\t3 4\u003cbr /\u003e\r\n\t\t2 5\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"output\"\u003e\r\n\t\u003cp\u003e\r\n\t\tOutput\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t4\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"input\"\u003e\r\n\t\u003cp\u003e\r\n\t\tInput\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t5 3\u003cbr /\u003e\r\n\t\t1 2\u003cbr /\u003e\r\n\t\t2 3\u003cbr /\u003e\r\n\t\t3 4\u003cbr /\u003e\r\n\t\t4 5\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"output\"\u003e\r\n\t\u003cp\u003e\r\n\t\tOutput\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t2\u003c/p\u003e\r\n\u003c/div\u003e"}}]}