P10309 "Cfz Round 2" Max of Distance

You are given a tree $G$ with $n$ nodes and an integer $E$. You need to construct an integer edge weight $w_i$ for each edge of the tree $G$, such that: - $1 \le w_i \le 10^9$; - Choose a node $u$ uniformly at random. The expected value of $\max\limits_{v=1}^n\operatorname{dis}(u,v)$, taken modulo $998244353$, is equal to $E$; or report that there is no solution. Here, $\operatorname{dis}(u,v)$ denotes the sum of edge weights on the simple path between nodes $u$ and $v$. If you do not know how to compute an expectation modulo $998244353$, please refer to [P2613 Template: Modulo of Rational Numbers](https://www.luogu.com.cn/problem/P2613).

The first line contains an integer $n$. The next $n-1$ lines each contain two positive integers $u_i,v_i$, indicating that there is an edge $(u_i,v_i)$ between nodes $u_i$ and $v_i$ in the tree $G$. The next line contains an integer $E$.

Output one line or $n-1$ lines: - If there is a solution, output $n-1$ lines, each containing an integer $w_i$, representing the edge weight of edge $(u_i,v_i)$ in your constructed tree $G$. - If there is no solution, output one line containing an integer $-1$. **Any output that satisfies the requirements will be accepted.**

#### "Sample Explanation #1" All values of $\operatorname{dis}$ are shown in the table below, where the red numbers are the maximum $\operatorname{dis}$ values for the node at the beginning of each row. |$\operatorname{dis}$|$1$|$2$|$3$| |:-:|:-:|:-:|:-:| |$1$|$0$|$1$|$\color{red}3$| |$2$|$1$|$0$|$\color{red}2$| |$3$|$\color{red}3$|$2$|$0$| You can verify that $E=\dfrac{3+2+3}{3}=\dfrac{8}{3}\equiv 665496238\pmod {998244353} $. #### Constraints For all testdata, $2\le n\le 10^5$, $1 \le u_i,v_i \le n$, $0\le E < 998244353$. It is guaranteed that the input forms a tree. **You can get the score for this problem only if you pass all test points.** Translated by ChatGPT 5