并不全

题目链接:传送门

接水果

一棵nn个点的树,有PP条路径,每条路径有权值cic_i

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

n,P,Q40000n, P, Q\le 40000

Solution

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

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

菜肴制作

一张nn个点,mm条边的DAG,求它的一个拓扑排序,满足编号越小的尽量排在越前面(不是字典序最小)

n,m105n, m\le 10^5

Solution

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

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

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

落忆枫音

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

答案对109+710^9+7取模

n105,m2105n\le 10^5, m\le 2*10^5

Solution

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

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

假设有一个 的环,那么不合法(要减掉)的方案数为i=2ndeg[i]i=1kdeg[ai]\displaystyle \frac{\prod_{i=2}^{n}deg[i]}{\prod_{i=1}^{k}deg[a_i]}

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

问题变成,计算从TTSS所有可能的路径,上面那个式子的和

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

开店

一棵nn个点,带边权的树,且每个点有权值xix_i

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

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

Solution

只口胡,不想写

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

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

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

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

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

亚瑟王

不太会,咕咕咕

实验比较

没看题,咕咕咕