{"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":"statement","value":{"format":"HTML","content":"Zihan is acquainted with a vast number of girls (not exceeding $2*10^5$), and their relationships form a tree-like structure. He has made a peculiar decision to engage in daily conversations with the girls. However, being afflicted with obsessive-compulsive tendencies, he imposes strict rules upon himself. On the first day, he can initiate a conversation with any girl at his discretion. But from the second day onwards, he is constrained to converse only with girls who are somehow connected to those he has conversed with previously. $\\\\$\n\nPrior to engaging in a conversation with each girl, Zihan meticulously assesses the size of the uncharted connected component in which the girl resides. Naturally, he experiences a surge of joy proportionate to the magnitude of the connected component (if the component encompasses n individuals, his joy score for that conversation amounts to n). Now, the inquiry at hand delves into the cumulative sum of Zihan\u0027s joy scores after he completes conversations with all the girls.$\\\\$\n\nLet\u0027s see the following example:\n\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/6d0bfe4a2927d636878e3963d70cdf22?v\u003d1683746026\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\n$\\\\$\n\nGirl $1$ and Girl $4$ are chatted already. If you choose girl $2$ to be the next girl, you will add $4$ scores for the connected component consisting of girls $2, 3, 5$ and $6$. If you choose the girl $9$, you will add $3$ scores for the connected component consisting of girls $7, 8$ and $9$. $\\\\$\nYour task is to maximize the number of Zihan\u0027s joy scores."}},{"title":"input","value":{"format":"HTML","content":"The first line contains an integer $n$ ($2 \\le n \\le 2 \\cdot 10^5$)-- the number of girls. $\\\\$\nEach of the next $n - 1$ lines describes the connect of girls.$\\\\$\nEdge $i$ is denoted by two integers $u_i$ and $v_i$($1 \\le u_i, v_i \\le n, u_i \\ne v_i$)-- the indices of girl $u_i$ and girl $v_i$ have somehow connects .$\\\\$\nIt is guaranteed that the given graph is a tree."}},{"title":"output","value":{"format":"HTML","content":"Print one integer — the maximum number of Zihan\u0027s joy scores."}},{"title":"sample 1","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\u003e9\n1 2\n2 3\n2 5\n2 6\n1 4\n4 9\n9 7\n9 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e36\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"sample 2","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\u003e5\n1 2\n1 3\n2 4\n2 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"note \u0026\u0026 hint","value":{"format":"HTML","content":"Note : The first example tree is shown in the problem statement.\nHint : We can perform a single depth-first search (DFS) to determine the sizes of all subtrees. Then, we can calculate the sum of the sizes for each subtree by root-DP, which will give us the answer."}}]}