树与序列问题
给定一棵树，树的点编号为1到n，以1为根，树的边有边权，定义s(x,y)=x到y路径上边权的最小值。
现需要构造一个1到n的排列p[]，使得∑i=1n?1s(p[i],p[i+1])\sum_{i=1}^{n-1}{s(p[i],p[i+1])}∑i=1n?1?s(p[i],p[i+1])最大，输出这个最大值即可。
示例1 输入3,6,7,5 输出77
示例2 输入4,3,9,6 输出297
树的边集不会直接给出，但会给出随机种子和构造方式，输入数据包含题干中的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
解：
因为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;
}
};