{"problem":{"name":"Tree Tree Tree","description":{"content":"You are given integers $N$ and $K$ such that $2\\leq K\\leq N$. > **Problem: potato** > We have a weighted rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root. > For each $2\\leq i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc167_f"},"statements":[{"statement_type":"Markdown","content":"You are given integers $N$ and $K$ such that $2\\leq K\\leq N$.\n\n> **Problem: potato**\n> We have a weighted rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root.\n> For each $2\\leq i\\leq N$, the parent of vertex $i$ is $p_{i}\\;(1\\leq p_{i}<i)$, and the edge connecting $i$ and $p_{i}$ has a weight of $q_{i-1}$.\n> Here, $q=(q_{1},q_{2},\\dots,q_{N-1})$ is a permutation of $(1,2,\\dots,N-1)$.\n> Let $cost(u,v)$ be the maximum weight of an edge in the simple path connecting vertices $u$ and $v$.\n> Find $\\sum_{u=1}^{N} \\sum_{v=u+1}^{N} cost(u,v)$.\n\n* * *\n\n> **Problem: tomato**\n> You are given an integer $a$ such that $1\\leq a\\lt K$. There are $\\frac{((N-1)!)^{2}}{K-1}$ possible pairs of $p$ and $q$ in the problem \"potato\" such that $p_{K}=a$. Find the sum, modulo $998244353$, of the answers to the problem over all those pairs.\n\nFor each $a=1,\\dots,K-1$, find the answer to the problem \"tomato\".\n\n## Constraints\n\n*   $2\\leq K\\leq N\\leq 10^{5}$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc167_f","tags":[],"sample_group":[["4 4","170\n170\n172"],["3 2","20"],["16 7","457991130\n457991130\n65525944\n418314090\n644126049\n676086428"]],"created_at":"2026-03-03 11:01:14"}}