树与序列问题

[编程题]树与序列问题

热度指数：1688 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵树，树的点编号为1到n，以1为根，树的边有边权，定义s(x,y)=x到y路径上边权的最小值。
现需要构造一个1到n的排列p[]，使得 $\sum_{i=1}^{n-1}{s(p[i],p[i+1])}$ 最大，输出这个最大值即可。

示例1

输入

3,6,7,5

输出

示例2

输入

4,3,9,6

输出

备注:

树的边集不会直接给出，但会给出随机种子和构造方式，输入数据包含题干中的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;
循环体结束
//////////////////////////////////////////////////////
输出一个整数，表示答案。
保证构造出的数据合法。
n<=200000,seed1,seed2,seed3<=1e10

算法知识视频讲解

Python

小小逐月者

class Solution:
    def work(self , n , seed1 , seed2 , seed3 ):
        res=0
        for i in range(n-1):
            seed4=((seed1+seed2)%998244353)*seed3%998244353
            res+=seed2*seed3%12131415
            seed3,seed2,seed1=seed2,seed1,seed4
        return res

发表于 2020-04-08 13:10:47 回复(3)