{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003eWe know that, a tree with $$$n$$$ nodes has $$$n-1$$$ edges. It is also possible to reach any node from any other node following a path of consecutive edges. Distance between two nodes is the number of edges in the direct path between them. So there must be a distance between two nodes such that, no other two nodes have greater distance then them. Your task is to find this distance.\u003c/p\u003e\n\n\u003cp\u003eFormally, given a tree with $$$n$$$ nodes, find out the maximum distance between any two nodes in the tree."}},{"title":"Input Specification","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoNormal\"\u003eThere are \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e≤ 10)\u003c/b\u003e test cases.\u003c/p\u003e \n \u003cp class\u003d\"MsoNormal\"\u003eFor each case, you will be given one integer \u003cb\u003en (2 ≤ n ≤ 30000)\u003c/b\u003e denoting the number of nodes in the tree. The nodes are 0-indexed (that means, they are numbered from \u003cb\u003e0\u003c/b\u003e to \u003cb\u003en-1\u003c/b\u003e). The next \u003cb\u003en-1\u003c/b\u003e lines will contain three integers \u003cb\u003ep q r (0 ≤ p, q \u0026lt; n, p ≠ q, 1 ≤ r ≤ 10000)\u003c/b\u003e denoting that node \u003cb\u003ep\u003c/b\u003e and \u003cb\u003eq\u003c/b\u003e are connected by an edge whose weight is \u003cb\u003er\u003c/b\u003e.\u003c/p\u003e \n "}},{"title":"Output Specification","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoNormal\"\u003ePrint the case number and the maximum distance. See sample for exact format.\n\u003c/p\u003e \n "}},{"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\u003e2\n4\n0 1 20\n1 2 30\n2 3 50\n5\n0 2 20\n2 1 10\n0 3 29\n0 4 50\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 100\nCase 2: 80\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}