题解 | #树与序列问题#

思路：

题目的主要信息：

• 一棵树编号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;
    }
};

复杂度分析：

• 时间复杂度：，一次遍历
• 空间复杂度：，常数级空间，无额外空间