模板题P3690
\(access\)是搞出一条端点为\(x,y\)的路径 , 且维护的是实子树的信息 . 由于题目比较简单 , \(access\)时还不需要更改其它信息
每条边有两个权值\(x_i,y_i\) , 在图上求一条 1 到 n 的路径 , 使得\(max\{x_i\}+max\{y_i\}\)最小 .
以\(y\)这一维排序依次加边 , 用\(LCT\)维护一条路径上\(x\)这一维的最大值 . 如果形成环而且当前插入的这条边小于环上最大值 , 就把环上最大值的那条边\(cut\) .
这样答案就是当前的\(y_i\)加上\(LCT\)中路径上最大的\(x_i\)
求经过一条边的路径数(即统计子树大小)
维护虚子树信息即可 , \(pushup\)时有\(size[x]=size[ls]+size[rs]+vsize[x]+1;\)
原文：https://www.cnblogs.com/lizehon/p/10622022.html