树与序列问题

[编程题]树与序列问题

热度指数：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

算法知识视频讲解

Unlimited_Blade_Works

因为s(x,y)=x到y路径上边权的最小值，想让答案尽可能大，我们肯定希望每个s（p[i],p[i+1]）都取到边权的最大值，但遗憾的是这是做不到，这个很好验证，自己随便画个图就知道了。那么现在的问题就是这个最大值是多少呢？
因为p为一个排列，因此我们可知每个点都至少要访问一次，因此所有边至少都要被遍历一遍。因此最短边必然会算入答案，且可能不止一次。而最大边最多出现一次（只有w=(p[i],p[i+1])时才可能出现）。为了使得答案尽可能大，我们希望所有边都出现一次。即最大的答案也就是所有边权的和。
不过以上最大值只是我们的猜想，是否有这样的排列p能使得答案=所有边权的和？若必然有，那么我们可以确定答案就是所有边权的和。

我们可以这样构造排列。任选一个点为起点进行bfs。不过bfs过程中，用优先队列维护，以边的大小作为比较准则（即边越大越先出队该点）。节点出队的顺序即为构造出的使答案最大的排列。

class Solution {
public:
    /**
     *
     * @param n int整型
     * @param seed1 long长整型
     * @param seed2 long长整型
     * @param seed3 long长整型
     * @return long长整型
     */
    long long work(int n, long long seed1, long long seed2, long long seed3) {
        // write code here
        long long res = 0;
        for(int i=1;i<n;i++){
            long long seed4=((seed1+seed2)%998244353)*seed3%998244353;
            res+=seed2*seed3%12131415;
            seed3=seed2;
            seed2=seed1;
            seed1=seed4;
        }
        return res;
    }
};

发表于 2020-04-22 17:01:10 回复(4)

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param seed1 long长整型 
     * @param seed2 long长整型 
     * @param seed3 long长整型 
     * @return long长整型
     */

    long long work(int n, long long seed1, long long seed2, long long seed3) {
        long long s = 0;
        for(int i=1;i<n;i++){
            long long seed4 = (((seed1+seed2)%998244353)*seed3)%998244353;
            s += (seed2*seed3)%12131415;
            seed3 = seed2;
            seed2 = seed1;
            seed1 = seed4;
        }
        return s;
    }
};

发表于 2020-09-03 16:42:29 回复(0)

Java

牛客255098966号

以示例输入为例

3,6,7,5
生成
      u -> v  = w
i=1   2 -> 1  = 35
i=2   3 -> 2  = 42

树结构 1 <-35- 2 <-42- 3

i的排列有以下6种
p[1,2,3]    1 -> 2  min(w)=35  2->3 min(w)=42    sum=77 p[1,3,2]    1 -> 3  min(w)=35  3->2 min(w)=42    sum=77
p[2,1,3]    2 -> 1  min(w)=35  1->3 min(w)=35    sum=70
p[2,3,1]    2 -> 3  min(w)=42  3->1 min(w)=35    sum=77
p[3,1,2]    3 -> 1  min(w)=35  1->2 min(w)=35    sum=70
p[3,2,1]    3 -> 2  min(w)=42  2->1 min(w)=35    sum=77
                                                 max(sum)=77
可以看出所求的最大值即所有边的权重和，直接利用题目给的生成树方法，求权值和就ok了

发表于 2020-06-12 21:48:17 回复(0)

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)