感谢olinr提供md文件
免得我整理格式了
1、求助
(help.cpp/c/pas)
【问题背景】
马上就要noip了，lrt同志(displaystyleegin{vmatrix} extrm{慌}&sqrt{ extrm{批}}\sqrt{ extrm{批}}& extrm{的}end{vmatrix}=慌得一批)，在某个透彻的晚四，找rqj整理OI知识点
【问题描述】
$ $rqj可是个dalaojuruo，他有一个神奇的技能，可以把两个毫无关系的知识点完美的联系在一起，耗费时间 (T_i), lrt表示不服，但是他必须花好长时间才能做到，一次耗时(t_i (t_i>T_i))，对于整个OI知识网络，共有m种联系，每一种可以将两个知识点相连，现在二人要把整个OI知识联系起来，为了锻炼lrt，lrt必须自己想至少k个联系，但rqj日理万机，耐心有限，他希望这几次联系中，时间最长的那次联系的时间最小，但是rqj懒的算QAQ，于是来请聪明的你帮他算一算
【输入】
输入文件名(help.in)
第一行为三个整数(n,k,m)，n为知识点数，m为联系个数，k如上述所示
接下来(m)行，每行四个整数(x_i y_i T_i t_i),
【输出】
输出仅一行，为最长联系时间的最小值
【输入样例】
4 2 5
3 4 9 12
3 2 8 10
4 2 6 7
2 1 7 9
3 1 4 5
【输出样例】
7
【数据范围】
对于(30\%)的数据，满足 (1le n le 100 , n-1le mle 150)
对于(50\%)的数据，满足 (1le n le 5000 , n-1le mle 10000)
对于(100\%)的数据，满足 (1le n le 100000 , n-1le mle 200000 , 1le T_i<t_ile 10^6)
【题解】
可以kruskal，可以二分答案
kruskal：按照lrt的排序，先加lrt后加rqj即可
二分答案：二分那个最大值，先把lrt所有能加的加入，（判断是否小于k如果小于k返回false）
然后把rqj所有能加的加入
维护并查集，判断最后是否连一起
2、心动
(olinr.cpp/c/pas)
【问题背景】
透彻人不干氨醛事，olinr走上了一条不归路
【问题描述】
$ $olinr很喜欢nmr，但是在二中的压迫下，透彻需谨慎，他必须合理安排在一起的时间，olinr和nmr在不同的教学楼，每天都要去不同的canteen打饭，他希望节约时间的前提下在一起走路的时间尽量长。
$ $现在已知二人的教学楼和两个目标canteen还有二中的地图，有n个路口，m条路，每条路经过需要一
定的时间。
$ $一句话概括题意：给出两个起点，终点，求最短路的最长公共路径
【输入】
输入文件名(olinr.in)
第一行为两个整数(n , m)，分别表示点数和边数
第二行为四个整数(x_1 y_1 x_2 y_2) 分别表示两个教学楼和食堂的编号(x_1 o y_1 x_2 o y_2)
接下来(m)行，每行三个整数(x_i y_i z_i) ，表示(x_i)与(y_i)有一条长度为(z_i)的边
【输出】
输出仅一行，为最长公共路径
【输入样例】
9 10
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1
【输出样例】
3
【数据范围】
对于(30\%)的数据，满足 (n le 100)
对于(60\%)的数据，满足 $n le 1000 $
对于(100\%)的数据，满足 (n le 1500)，保证没有重边和自环
【题解】
先从s1,t1,s2,t2跑四遍dij，求出哪些边在nmr的路上
然后在olinr的最短路DAG上标出这些边
求最长链即可
3、透彻
(game.cpp/c/pas)
【问题背景】
奥赛部终于放假了， 像olinr这种人，当然选择透彻啦！
【问题描述】
$ $olinr正在卧室的电脑前透彻。。。
$ $olinr打算通关一个游戏，从而获得金币买装备。这个游戏有n个场景，有许多通关途径。具体来说，某些场景
可以通过分支到达其它场景，这些场景构成了一棵树。olinr此时在根节点，他要到叶子节点即可通关。每个场景
都有一些金币，olinr可以获得它们。由于太久没放假，olinr积累了大量的能力值，使得他可以同时通关(k)次，当
然，同一个场景再次走到就没有金币了QAQ（一个场景的金币只能获得一次），不过偷车时间宝贵，他急忙问
你，他最多能获得多少金币，你要在(1s) 内告诉他欧（1号节点为根节点）
【输入】
输入文件名game.in$
第一行为两个整数(n , k)，分别表示点数和次数
第二行为(n)个整数，分别表示每个场景的金币数量
接下来(n-1)行，每行两个整数(x_i y_i) ，表示(x_i)场景有一个分支通向(y_i)场景
【输出】
输出仅一行，为最大金币获得数量
【输入样例】
5 2
4 3 2 1 1
1 2
1 5
2 3
2 4
【输出样例】
10
【数据范围】
对于(10\%)的数据，满足$nle10 $
对于额外(15\%)的数据，满足(k=1)
对于额外(15\%)的数据，满足是一条链
有额外(\%5)的数据，(k=2)
对于(70\%)的数据，满足(nle 50000)
对于(100\%)的数据，满足(nle 200000,1le每个点金币数le2^{31}-1)
【题解】
是bzoj的某道题
线段树+DFS序太麻烦
可以用长链剖分做
考虑这样的：
/
/
[x]
/ |
/ |
[3] [4] [5]
可以转化为
/ / /
/ / /
/ / [x]
/ / |
/ | |
[3] [4] [5]
因为根据贪心，你选这可子树肯定先选5，然后选4，然后选3，既然选5那就是5+x
这样子就慢慢地把树变成了森林，且森林中每个树都只有一个节点，且树的数量和叶子节点相同
把树放到数组中sort取前k大就行了