「HNOI2015」Brief Solution

并不全

题目链接：传送门

接水果

一棵$n$个点的树，有$P$条路径，每条路径有权值$c_i$

$Q$次询问$(x, y, k)$，每次询问在所有包含于路径$(x, y)$的路径中，第$k$小的权值

$n, P, Q\le 40000$

Solution

显然可以直接二分答案，但是直接在线check需要二维线段树维护，不好搞，于是离线整体二分

整体二分里面套了一个二维数点，随便扫一下就可以了

菜肴制作

一张$n$个点，$m$条边的DAG，求它的一个拓扑排序，满足编号越小的尽量排在越前面（不是字典序最小）

$n, m\le 10^5$

Solution

显然越靠后面的位置放越大的数会更优，建反图跑拓扑排序，使得字典序尽量大，再倒着输出即可

稍微证明一下为什么是这样的

考虑当前可以放在最后一个的最大的数，如果它不放在最后，那真正放过去的那个数会比它小，显然不会更优

落忆枫音

一张$n$个点，$m$条边的DAG，再往上加一条边$(S, T)$，求得到的图外向生成树的个数

答案对$10^9+7$取模

$n\le 10^5, m\le 2*10^5$

Solution

记$deg[i]$表示$i$的入边个数，考虑每个点的父亲是谁，那么一个DAG的方案数为$\displaystyle \prod_{i=2}^{n}deg[i]$

加上一条新边之后，如果还这么算的话，可能会出现环，考虑把所有环的方案减掉

假设有一个的环，那么不合法（要减掉）的方案数为$\displaystyle \frac{\prod_{i=2}^{n}deg[i]}{\prod_{i=1}^{k}deg[a_i]}$

环上的点都钦定了父亲，剩下所有点的父亲随便选

问题变成，计算从$T$到$S$所有可能的路径，上面那个式子的和

因为原图是个DAG，直接拓扑排序dp即可

开店

一棵$n$个点，带边权的树，且每个点有权值$x_i$

$Q$次询问$(x, l, r)$，每次询问从$x$出发，到所有点权$\in [l, r]$的点的路径长度和

$n, Q\le 2*10^5$

Solution

只口胡，不想写

点权$\in [l, r]$的这个限制显然可以用主席树搞掉

问题变成，你有一个点集，每次询问一个点到所有点集中的点的距离和

直接算不好算，根据树上问题的套路，显然$x$到$y$的路径长度可以转化为$\mathrm{dis}(x) + \mathrm{dis}(y) - 2*\mathrm{dis}(lca_{x, y})$

那么就是要求$\mathrm{dis}(lca_{x, y})$，显然这个东西就是$x$到根的路径和$y$到根的路径的交

树剖，一开始把每个点到根的路径全部加一下，查询就直接查那个点的权值即可。也就是区间加，单点查询

亚瑟王

不太会，咕咕咕

实验比较

没看题，咕咕咕