给定一棵树,树的点编号为1到n,以1为根,树的边有边权,定义s(x,y)=x到y路径上边权的最小值。
现需要构造一个1到n的排列p[],使得最大,输出这个最大值即可。
3,6,7,5
77
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
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; } };
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; } };
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了