[ZSHOI-R1] 巡城

Luogu

IDLGP9454

Time1000ms

Memory256MB

DifficultyP6

动态规划 DP期望

国王为了能够集中自己的权力，稳固城邦，她对国家道路设计要求十分严苛，**任何两个城市之间的路径至多只有一条不经过首都**，虽然但是，没有人知道为什么这样能够更好地稳固 X 国。有一天，X 国国王决定巡视所有的城市，她通过无线电在巡城前一天向所有的城市通知了这个好消息。热情的群众们也积极地做出了响应，准备迎接国王的到来。国王一天只能造访一座城市，而且第一天她会从首都开始。在之后的每一天，她会随机从与她所在城市直接相连的城市中**等概率**地选择一个她**没有前往过的城市**前往。如果不存在这样的城市，她会立即**原路返回**，从她来这个城市的路回去，再重复上述操作，因为有携带宇宙射线的传送门，这个过程**不消耗时间**。爱戴她的群众们想要知道，他们的国王第一次到达他们所在城市的日期（她造访首都的那一天为 $1$，之后每一天一次加 $1$）的期望是多少，答案对 $998244353$ 取模。保证城市构成的图是连通图，无自环与重边，且首都编号为 $1$。 ## Input 第一行有两个数 $n,m$，代表X国的城市数和路径数。接下来的 $m$ 行，每行两个数 $u,v$ 表示城市的一条路径。 ## Output 共 $1$ 行，$n$ 个数。第 $i$ 个数代表 $i$ 号城市的期望。 [samples] ## Background 在 X 国国王多年的建设之下，她的国家发生了质的蜕变，从众多 $n$ 座城市却只有 $n-1$ 条道路的国家中脱颖而出。也就是说，X 国不再是一棵树了，而是一张图。 ## Note 对于所有的数据点，$1\leqslant n\leqslant 5 \times 10^5$，$1\leqslant m \leqslant 6 \times 10^5$。 | 数据点 | n | m | | :----------: | :----------: | :----------: | | 1~2 | $5$ | $7$ | | 3~5 | $\leqslant10^4$ | $n-1$ | | 6~8 | $\leqslant10^4$ | $n$ | | 9~10 | $\leqslant10^4$ | $2n-3$ | | 11~15 | $\leqslant10^4$ | $\leqslant2\times10^4$ | | 16~20 | $\leqslant5\times10^5$ | $\leqslant6\times10^5$ |

Samples

Input #1

3 2
1 2
2 3

Output #1

1 2 3

Input #2

Output #2

1 2 499122180 499122180

Input #3

Output #3

1 249561092 249561092 249561091 249561092

API Response (JSON)

{
  "problem": {
    "name": "[ZSHOI-R1] 巡城",
    "description": {
      "content": "国王为了能够集中自己的权力，稳固城邦，她对国家道路设计要求十分严苛，**任何两个城市之间的路径至多只有一条不经过首都**，虽然但是，没有人知道为什么这样能够更好地稳固 X 国。 有一天，X 国国王决定巡视所有的城市，她通过无线电在巡城前一天向所有的城市通知了这个好消息。热情的群众们也积极地做出了响应，准备迎接国王的到来。 国王一天只能造访一座城市，而且第一天她会从首都开始。 在之后的每一天，",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9454"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "国王为了能够集中自己的权力，稳固城邦，她对国家道路设计要求十分严苛，**任何两个城市之间的路径至多只有一条不经过首都**，虽然但是，没有人知道为什么这样能够更好地稳固 X 国。\n\n有一天，X 国国王决定巡视所有的城市，她通过无线电在巡城前一天向所有的城市通知了这个好消息。热情的群众们也积极地做出了响应，准备迎接国王的到来。\n\n国王一天只能造访一座城市，而且第一天她会从首都开始。\n\n在之后的每一天，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments