思路：
题目的主要信息：
- 一棵树编号1到n，其中1为根，树的每条边有权值
，其中
为x节点到y节点经过的边的权值
- 构造一个排列p，使得
最大，且输出这个最大值
树的边集不会直接给出，但会给出随机种子和构造方式，输入数据包含题干中的n和三个随机种子seed1，seed2，seed3.
构造方式如下
////////////////////////////
定义数组u[],v[],w[] //u[i],v[i]分别表示第i条边的两个端点，w[i]表示第i条边的边权。
定义变量seed4.
定义循环变量 i 从1到n-1
循环体开始
seed4=((seed1+seed2)%998244353)*seed3%998244353;
u[i]=i+1;
v[i]=(seed4%i)+1;
w[i]=seed2*seed3%12131415;
seed3=seed2;
seed2=seed1;
seed1=seed4;
循环体结束
//////////////////////////////////////////////////////方法一：构造相加
具体做法：
首先我们按照题目中给的流程构造这个棵树及各个边权。暴力每种排列用dfs求上述最大值，复杂度会过大，因为最大数据的时候复杂度至少大于（)，显然是不可行的，我们可以观察规律。
不管怎么组建树，如果我们每次都能取到树权值最大的一边，那么我们即可取到题目要求的最大值，可惜的是每次取的是路径上最小的一边，因此上述猜想可以被轻易否定。但是我们可以想到的是，最大权值边最多可以出现一次，就是
的时候，后面再接上其他边的时候会取较小值。当排除掉最大边以后，次大边也最多出现一次，即
这个是次大边。同理，我们可以构造出这样一个排列，从最大边开始，后续每个边都只出现一次，那么这就是最大值，只要不让最小边多次出现就是最大值。
因为所有边权值的和就是我们要求的答案，一个遍历相加即可。
class Solution {
public:
long long work(int n, long long seed1, long long seed2, long long seed3) {
long long res = 0;
long long mod1 = 998244353;
long long mod2 = 12131415;
vector<int> u(n, 0); //记录相连的点
vector<int> v(n, 0);
vector<int> w(n, 0); //记录权值
for(int i = 1; i < n; i++){ //按照流程算每个边权
long long seed4 = ((seed1 + seed2) % mod1 * seed3) % mod1;
u[i] = i + 1;
v[i] = (seed4 % i) + 1;
w[i] = (seed2 * seed3) % mod2;
seed3 = seed2;
seed2 = seed1;
seed1 = seed4;
}
for(int i = 0; i < n; i++) //求权值和
res += w[i];
return res;
}
};复杂度分析：
- 时间复杂度：
，两次单独的循环
- 空间复杂度：
方法二：直接计算
具体做法：
从方法一得到我们要求的答案就是所有边的权值总和，那我们不必完整构造出这棵树，只需要在构造的循环中将计算出的权值累加即可，至于什么节点怎么连的，完全不用管。
class Solution {
public:
long long work(int n, long long seed1, long long seed2, long long seed3) {
long long res = 0;
long long mod1 = 998244353;
long long mod2 = 12131415;
for(int i = 1; i < n; i++){ //按照流程算每个边权
long long seed4 = ((seed1 + seed2) % mod1 * seed3) % mod1;
res += (seed2 * seed3) % mod2; //直接求边权和
seed3 = seed2;
seed2 = seed1;
seed1 = seed4;
}
return res;
}
};复杂度分析：
- 时间复杂度：
- 空间复杂度：
，常数级空间，无额外空间
京公网安备 11010502036488号