309939: CF1762E. Tree Sum
Memory Limit：256 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Tree Sum
题目描述
Let us call an edge-weighted tree with $ n $ vertices numbered from $ 1 $ to $ n $ good if the weight of each edge is either $ 1 $ or $ -1 $ and for each vertex $ i $ , the product of the edge weights of all edges having $ i $ as one endpoint is $ -1 $ . You are given a positive integer $ n $ . There are $ n^{n-2} \cdot 2^{n-1} $ distinct $ ^\dagger $ edge-weighted trees with $ n $ vertices numbered from $ 1 $ to $ n $ such that each edge is either $ 1 $ or $ -1 $ . Your task is to find the sum of $ d(1,n)^\ddagger $ of all such trees that are good. Since the answer can be quite large, you only need to find it modulo $ 998\,244\,353 $ . $ ^\dagger $ Two trees are considered to be distinct if either: - there exists two vertices such that there is an edge between them in one of the trees, and not in the other. - there exists two vertices such that there is an edge between them in both trees but the weight of the edge between them in one tree is different from the one in the other tree. Note that by [Cayley's formula](https://rb.gy/hho7vu), the number of trees on $ n $ labeled vertices is $ n^{n-2} $ . Since we have $ n-1 $ edges, there are $ 2^{n-1} $ possible assignment of weights(weight can either be $ 1 $ or $ -1 $ ). That is why total number of distinct edge-weighted tree is $ n^{n-2} \cdot 2^{n-1} $ . $ ^\ddagger $ $ d(u,v) $ denotes the sum of the weight of all edges on the unique simple path from $ u $ to $ v $ .输入输出格式
输入格式
The first and only line of input contains a single integer $ n $ ( $ 1 \leq n \leq 5 \cdot 10^5 $ ).
输出格式
The only line of output should contain a single integer, the required answer, modulo $ 998\,244\,353 $ .
输入输出样例
输入样例 #1
2输出样例 #1
998244352输入样例 #2
1输出样例 #2
0输入样例 #3
4输出样例 #3
998244343输入样例 #4
10输出样例 #4
948359297输入样例 #5
43434输出样例 #5
86232114说明
In the first test case, there is only $ 1 $ distinct good tree. The value of $ d(1,2) $ for that tree is $ -1 $ , which is $ 998\,244\,352 $ under modulo $ 998\,244\,353 $ . In the second test case, the value of $ d(1,1) $ for any tree is $ 0 $ , so the answer is $ 0 $ . In the third test case, there are $ 16 $ distinct good trees. The value of $ d(1,4) $ is: - $ -2 $ for $ 2 $ trees; - $ -1 $ for $ 8 $ trees; - $ 0 $ for $ 4 $ trees; - $ 1 $ for $ 2 $ trees. The sum of $ d(1,4) $ over all trees is $ 2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10 $ , which is $ 998\,244\,343 $ under modulo $ 998\,244\,353 $ .Input
题意翻译
一个加权树有 $n$ 个结点，每条边边权为 $1$ 或 $-1$。一共有 $n^{n-2}\times2^{n-1}$ 个这样的树，如果每个结点所有的边边权之积为 $-1$，那么定义这个树是好的。对于所有好的树，求 $dis(1,n)$ 的和，答案对 $998244353$ 取模。 $\text{Translated by jesse1216.}$Output
**树和**
**题目描述**
定义一个有 $ n $ 个顶点（编号从 1 到 $ n $）的带权树为“好的”，如果每条边的权重是 1 或 -1，并且对于每个顶点 $ i $，所有以 $ i $ 为一个端点的边的权重乘积为 -1。给定一个正整数 $ n $，有 $ n^{n-2} \cdot 2^{n-1} $ 个不同的带权树满足上述条件。任务是找出所有这些“好的”树中 $ d(1,n) $ 的和。由于答案可能很大，只需要求出其对 998,244,353 取模的结果。
其中 $ d(u,v) $ 表示从 $ u $ 到 $ v $ 的唯一简单路径上所有边的权重之和。
**输入输出格式**
**输入格式**
输入包含一个整数 $ n $（$ 1 \leq n \leq 5 \cdot 10^5 $）。
**输出格式**
输出包含一个整数，即所需的答案，对 998,244,353 取模。
**输入输出样例**
**输入样例 #1**
```
2
```
**输出样例 #1**
```
998244352
```
**输入样例 #2**
```
1
```
**输出样例 #2**
```
0
```
**输入样例 #3**
```
4
```
**输出样例 #3**
```
998244343
```
**输入样例 #4**
```
10
```
**输出样例 #4**
```
948359297
```
**输入样例 #5**
```
43434
```
**输出样例 #5**
```
86232114
```
**说明**
在第一个测试案例中，只有一个不同的“好的”树。该树的 $ d(1,2) $ 值为 -1，模 998,244,353 下的结果为 998,244,352。
在第二个测试案例中，任何树的 $ d(1,1) $ 值为 0，因此答案为 0。
在第三个测试案例中，有 16 个不同的“好的”树。$ d(1,4) $ 的值为：
- 对于 2 个树，值为 -2；
- 对于 8 个树，值为 -1；
- 对于 4 个树，值为 0；
- 对于 2 个树，值为 1。
所有树中 $ d(1,4) $ 的和为 $ 2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10 $，模 998,244,353 下的结果为 998,244,343。**树和** **题目描述** 定义一个有 $ n $ 个顶点（编号从 1 到 $ n $）的带权树为“好的”，如果每条边的权重是 1 或 -1，并且对于每个顶点 $ i $，所有以 $ i $ 为一个端点的边的权重乘积为 -1。给定一个正整数 $ n $，有 $ n^{n-2} \cdot 2^{n-1} $ 个不同的带权树满足上述条件。任务是找出所有这些“好的”树中 $ d(1,n) $ 的和。由于答案可能很大，只需要求出其对 998,244,353 取模的结果。 其中 $ d(u,v) $ 表示从 $ u $ 到 $ v $ 的唯一简单路径上所有边的权重之和。 **输入输出格式** **输入格式** 输入包含一个整数 $ n $（$ 1 \leq n \leq 5 \cdot 10^5 $）。 **输出格式** 输出包含一个整数，即所需的答案，对 998,244,353 取模。 **输入输出样例** **输入样例 #1** ``` 2 ``` **输出样例 #1** ``` 998244352 ``` **输入样例 #2** ``` 1 ``` **输出样例 #2** ``` 0 ``` **输入样例 #3** ``` 4 ``` **输出样例 #3** ``` 998244343 ``` **输入样例 #4** ``` 10 ``` **输出样例 #4** ``` 948359297 ``` **输入样例 #5** ``` 43434 ``` **输出样例 #5** ``` 86232114 ``` **说明** 在第一个测试案例中，只有一个不同的“好的”树。该树的 $ d(1,2) $ 值为 -1，模 998,244,353 下的结果为 998,244,352。 在第二个测试案例中，任何树的 $ d(1,1) $ 值为 0，因此答案为 0。 在第三个测试案例中，有 16 个不同的“好的”树。$ d(1,4) $ 的值为： - 对于 2 个树，值为 -2； - 对于 8 个树，值为 -1； - 对于 4 个树，值为 0； - 对于 2 个树，值为 1。 所有树中 $ d(1,4) $ 的和为 $ 2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10 $，模 998,244,353 下的结果为 998,244,343。
**题目描述**
定义一个有 $ n $ 个顶点（编号从 1 到 $ n $）的带权树为“好的”，如果每条边的权重是 1 或 -1，并且对于每个顶点 $ i $，所有以 $ i $ 为一个端点的边的权重乘积为 -1。给定一个正整数 $ n $，有 $ n^{n-2} \cdot 2^{n-1} $ 个不同的带权树满足上述条件。任务是找出所有这些“好的”树中 $ d(1,n) $ 的和。由于答案可能很大，只需要求出其对 998,244,353 取模的结果。
其中 $ d(u,v) $ 表示从 $ u $ 到 $ v $ 的唯一简单路径上所有边的权重之和。
**输入输出格式**
**输入格式**
输入包含一个整数 $ n $（$ 1 \leq n \leq 5 \cdot 10^5 $）。
**输出格式**
输出包含一个整数，即所需的答案，对 998,244,353 取模。
**输入输出样例**
**输入样例 #1**
```
2
```
**输出样例 #1**
```
998244352
```
**输入样例 #2**
```
1
```
**输出样例 #2**
```
0
```
**输入样例 #3**
```
4
```
**输出样例 #3**
```
998244343
```
**输入样例 #4**
```
10
```
**输出样例 #4**
```
948359297
```
**输入样例 #5**
```
43434
```
**输出样例 #5**
```
86232114
```
**说明**
在第一个测试案例中，只有一个不同的“好的”树。该树的 $ d(1,2) $ 值为 -1，模 998,244,353 下的结果为 998,244,352。
在第二个测试案例中，任何树的 $ d(1,1) $ 值为 0，因此答案为 0。
在第三个测试案例中，有 16 个不同的“好的”树。$ d(1,4) $ 的值为：
- 对于 2 个树，值为 -2；
- 对于 8 个树，值为 -1；
- 对于 4 个树，值为 0；
- 对于 2 个树，值为 1。
所有树中 $ d(1,4) $ 的和为 $ 2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10 $，模 998,244,353 下的结果为 998,244,343。**树和** **题目描述** 定义一个有 $ n $ 个顶点（编号从 1 到 $ n $）的带权树为“好的”，如果每条边的权重是 1 或 -1，并且对于每个顶点 $ i $，所有以 $ i $ 为一个端点的边的权重乘积为 -1。给定一个正整数 $ n $，有 $ n^{n-2} \cdot 2^{n-1} $ 个不同的带权树满足上述条件。任务是找出所有这些“好的”树中 $ d(1,n) $ 的和。由于答案可能很大，只需要求出其对 998,244,353 取模的结果。 其中 $ d(u,v) $ 表示从 $ u $ 到 $ v $ 的唯一简单路径上所有边的权重之和。 **输入输出格式** **输入格式** 输入包含一个整数 $ n $（$ 1 \leq n \leq 5 \cdot 10^5 $）。 **输出格式** 输出包含一个整数，即所需的答案，对 998,244,353 取模。 **输入输出样例** **输入样例 #1** ``` 2 ``` **输出样例 #1** ``` 998244352 ``` **输入样例 #2** ``` 1 ``` **输出样例 #2** ``` 0 ``` **输入样例 #3** ``` 4 ``` **输出样例 #3** ``` 998244343 ``` **输入样例 #4** ``` 10 ``` **输出样例 #4** ``` 948359297 ``` **输入样例 #5** ``` 43434 ``` **输出样例 #5** ``` 86232114 ``` **说明** 在第一个测试案例中，只有一个不同的“好的”树。该树的 $ d(1,2) $ 值为 -1，模 998,244,353 下的结果为 998,244,352。 在第二个测试案例中，任何树的 $ d(1,1) $ 值为 0，因此答案为 0。 在第三个测试案例中，有 16 个不同的“好的”树。$ d(1,4) $ 的值为： - 对于 2 个树，值为 -2； - 对于 8 个树，值为 -1； - 对于 4 个树，值为 0； - 对于 2 个树，值为 1。 所有树中 $ d(1,4) $ 的和为 $ 2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10 $，模 998,244,353 下的结果为 998,244,343。