{"problem":{"name":"Preserve Diameter","description":{"content":"We have a tree $G$ with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge of $G$ connects Vertex $a_i$ and Vertex $b_i$. Consider adding zero or more edges in $G$, and let $H$ be the graph resulted. ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"hitachi2020_f"},"statements":[{"statement_type":"Markdown","content":"We have a tree $G$ with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge of $G$ connects Vertex $a_i$ and Vertex $b_i$.\nConsider adding zero or more edges in $G$, and let $H$ be the graph resulted.\nFind the number of graphs $H$ that satisfy the following conditions, modulo $998244353$.\n\n*   $H$ does not contain self-loops or multiple edges.\n*   The diameters of $G$ and $H$ are equal.\n*   For every pair of vertices in $H$ that is not directly connected by an edge, the addition of an edge directly connecting them would reduce the diameter of the graph.\n\n## Constraints\n\n*   $3 \\le N \\le 2 \\times 10^5$\n*   $1 \\le a_i, b_i \\le N$\n*   The given graph is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$\\vdots$\n$a_{N-1}$ $b_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"hitachi2020_f","tags":[],"sample_group":[["6\n1 6\n2 1\n5 2\n3 4\n2 3","3\n\nFor example, adding the edges $(1, 5), (3, 5)$ in $G$ satisfies the conditions."],["3\n1 2\n2 3","1\n\nThe only graph $H$ that satisfies the conditions is $G$."],["9\n1 2\n2 3\n4 2\n1 7\n6 1\n2 5\n5 9\n6 8","27"],["19\n2 4\n15 8\n1 16\n1 3\n12 19\n1 18\n7 11\n11 15\n12 9\n1 6\n7 14\n18 2\n13 12\n13 5\n16 13\n7 1\n11 10\n7 17","78732"]],"created_at":"2026-03-03 11:01:14"}}