题意link.题解一个好想一点的正解。考虑到可能连锁爆炸，我们不能通过一个单纯的二分来解决问题。考虑dp。记\(f(i)\)为第\(i\)个点爆炸，最远能引爆到哪个坐标小于它的点。\(g(i)\)为第\(i\)个点爆炸，最远能引爆到哪个坐标大于它的点。我们以\(f\)为例，\(g\)可以通

思路：首先可以先考虑没有换根的情况。先将树拍到dfn序上，那么一个子树\(u\)的所有点的dfn序区间为\([dfn_u,dfn_u+siz_u-1]\)。那么询问变为：每次给定两个区间\([l_1,r_1],[l_2,r_2]\)，对于在第一个区间内的点\(x\)和在第二个区间的点\(y\)，若\((x,y)\)有贡献，当且仅

P5365SNOI2017英雄联盟基本思路刚洗完澡做的，脑子转不动了。疑似开始自动化思考了，状态转移方程是这一坨\(F[i][j]*=F[i-1][j-k*w[i]]\)事实上根本不对。首先当前的方案数完全没有体现出来，只乘了之前的方案数，而且这是一个最优性问题，不是计数问题，要在两种状况中做出选

一个简单的询问显然这个询问并不简单如果做过莫比乌斯反演入门题problemb就会想到利用容斥将询问拆成四个那么我们现在的问题变成如何求[1,l][1,r]两个区间之间的答案，那么也是直接用莫队即可，只是维护的是两个区间的右端点，和原来的莫队有一些不一样，但是大体相同。#include<

P5025SNOI2017炸弹不难看出本题是可以转化为图论模型的：建立\(n\)个点代表\(n\)个炸弹，如果第\(i\)个炸弹能直接引爆第\(j\)个炸弹，就连边\(i\toj\)。这样的图论模型很好地刻画了原题中引爆的传递性，题意中第\(i\)个炸弹能直接/间接引爆第\(j\)个炸弹直接等价于

链接：https://www.luogu.com.cn/problem/P5366题目描述:有\(n\)个数\(1\)到\(n\)，给定\(q\)组询问，每组询问形如求选择一些数且必须选\(x\)且最大公约数为\(G\),最小公倍数为

先来看板子题：CF786B可以发现，如果对着区间内的每一个点都建一条边，然后跑最短路，我们无论是在空间还是时间复杂度上都是过不去的。因此，我们请出老朋友线段树。参考上图。