「Cfz Round 2」Max of Distance

Luogu

IDLGP10309

Time1000ms

Memory512MB

DifficultyP4

数学洛谷原创Special JudgeO2优化树的直径树论构造洛谷月赛

给定一棵包含 $n$ 个结点的树 $G$ 和一个整数 $E$。你需要构造树 $G$ 中每条边的整数边权 $w_i$，满足： - $1 \le w_i \le 10^9$； - 均匀随机选择一个结点 $u$，$\max\limits_{v=1}^n\operatorname{dis}(u,v)$ 的期望对 $998244353$ 取模的值等于 $E$；或报告无解。其中，$\operatorname{dis}(u,v)$ 表示结点 $u,v$ 之间简单路径上的边权和。如果你不知道如何计算期望对 $998244353$ 取模的结果，请移步 [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)。 ## Input 第一行输入一个整数 $n$。接下来 $n-1$ 行，每行输入两个正整数 $u_i,v_i$，表示树 $G$ 中结点 $u_i,v_i$ 之间存在一条边 $(u_i,v_i)$。接下来一行，输入一个整数 $E$。 ## Output 输出一行或 $n-1$ 行： - 若有解，则输出 $n-1$ 行，每行输出一个整数 $w_i$，表示你构造的树 $G$ 中边 $(u_i,v_i)$ 的边权； - 若无解，则输出一行，包含一个整数 $-1$。 **所有满足要求的输出均可通过。** [samples] ## Note #### 「样例解释 #1」所有 $\operatorname{dis}$ 的值如下表，其中标红的是行首结点的 $\operatorname{dis}$ 的最大值。 |$\operatorname{dis}$|$1$|$2$|$3$| |:-:|:-:|:-:|:-:| |$1$|$0$|$1$|$\color{red}3$| |$2$|$1$|$0$|$\color{red}2$| |$3$|$\color{red}3$|$2$|$0$| 可以验证，$E=\dfrac{3+2+3}{3}=\dfrac{8}{3}\equiv 665496238\pmod {998244353} $。 #### 「数据范围」对于所有数据，$2\le n\le 10^5$，$1 \le u_i,v_i \le n$，$0\le E < 998244353$，保证输入数据形成一棵树。 **只有你通过本题的所有测试点，你才能获得本题的分数。**

Samples

Input #1

Output #1

1
2

API Response (JSON)

{
  "problem": {
    "name": "「Cfz Round 2」Max of Distance",
    "description": {
      "content": "给定一棵包含 $n$ 个结点的树 $G$ 和一个整数 $E$。 你需要构造树 $G$ 中每条边的整数边权 $w_i$，满足： - $1 \\le w_i \\le 10^9$； - 均匀随机选择一个结点 $u$，$\\max\\limits_{v=1}^n\\operatorname{dis}(u,v)$ 的期望对 $998244353$ 取模的值等于 $E$； 或报告无解。 其中，$\\operat",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10309"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一棵包含 $n$ 个结点的树 $G$ 和一个整数 $E$。\n\n你需要构造树 $G$ 中每条边的整数边权 $w_i$，满足：\n\n- $1 \\le w_i \\le 10^9$；\n- 均匀随机选择一个结点 $u$，$\\max\\limits_{v=1}^n\\operatorname{dis}(u,v)$ 的期望对 $998244353$ 取模的值等于 $E$；\n\n或报告无解。\n\n其中，$\\operat...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments