标签 树链剖分 下的文章

link

有一个无向带权图,由两棵树A,B组成,若A树中有边(u,v),则B树中有边(u,v)。并且两棵树的每个对应点都有边直接连接。

q次询问求两点间最短路。

- 阅读剩余部分 -

题意

有n个村庄,连成一棵树。

有m次操作,每次形如$u,v,w$,表示给从u到v的所有村庄颁发一个类型为w的证书,求每个村庄得到哪类证书的个数最多。若有多个输出类型最小值,若没有证书输出0

$n,m,w\le 10^5$

- 阅读剩余部分 -

题意

给定一棵n点的树,每个点有点权$w_i$。每次给定u,v,求$(\sum_{i=1}^n\sum_{j=1}^nf(i,j)) \mod 10^9+7$,其中当i到j的路径和u到v的路径有交集时$f(i,j)=w_iw_j$,否则$f(i,j)=0$

- 阅读剩余部分 -