标签-差分

题意给出一棵树,定义 $\mathrm{dep}[i]$ 为 $i$ 的深度,$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(x y)}$ 的询问,求 $\sum\limits_{i \le x} \text{dep}(\text{LCA}(i,y))^k$ 。其中点数 $N\le 50000$ ,询问数 $M\le 50000$ 。...
   题解    2 条评论
NOI/NOI+/CTSC
题意给出一棵树,定义 $\mathrm{dep}[i]$ 为 $i$ 的深度,$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(l r z)}$ 的询问,求 $\sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]$ 。其中点数 $N\le 50000$ ,询问数 $M\l...
   题解    0 条评论
NOI/NOI+/CTSC