给定一棵树,树的点编号为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
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了