给定一个 n 个点 m 条边且有边权的 DAG，进行 c 次询问，每次给定 u,v,l,r，求出从 u 开始只经过边权在 [l,r] 内的边是否能到达 v。
第一眼看上去是高端数据结构题，然后想了一年完全不会。。。
正解非常简单，但是可能真的不太容易想到。
设 dp_{i,j} 表示从第 i 个点开始只经过 [l_j,r_j] 中的边是否可以到达 v_j。
只需要计算这个 dp 数组即可得到答案，而这是非常容易的。再用 bitset 优化一下即可。
时间复杂度 O\left(\dfrac{(n+m)c}{\omega}\right)。
如果要节省空间可以把每 \omega=64 个询问分成一组在 DAG 上跑，直接用 ull 存就行了。
其主要思想可以看作把两维换一下（抽象）。
具体来说，暴力的做法是对于每个询问在 DAG 上做一遍，现在把它改为按照某种顺序加入 DAG 中的边，并计算它对询问的影响。
给定一棵 n 个点的有根树，根为 1。每个点 u 有两个正整数权值 a_u,b_u 和一个颜色 c_i\in\{0,1\}。
要求选一个点的子集 S，满足：
求 \sum\limits_{u\in S} a_u\le m 的情况下 \sum b_u 的最大值。
对于每个点 u 求出只保留 u 的子树时的答案。
设 dp_{u,i,j} 表示考虑 u 的子树，最顶上选的一层点颜色均为 i 的答案，且当前 \sum\limits_{u\in S} a_u=j。
但直接 dp 的时间复杂度为 O(nm^2)，无法通过。
我们希望避免两个 dp 数组的合并，因为合并一次就会带来 O(m^2) 的巨大代价。
设 dfs 函数可以计算 dp_u，考虑按照如下方式进行计算。
function dfs(u, z)
if u is not leaf then
hv = (heavy child of u)
z1 <- dfs(hv, z)
for v in {children of u} / {hv} do
z1[0] <- dfs(d, z1[0])[0]
z1[1] <- dfs(d, z1[1])[1]
end for
else
z1[0] <- z
z1[1] <- z
end if
for i = 0 to m - a[u] do
chmax(z1[c[u]][i + a[u]], z1[c[u] ^ 1][i] + b[u])
end for
return z1
dfs 函数的意义是，考虑 u 的子树，给定序列 z 表示初始值，返回两个序列分别表示 u 的子树内选择的最顶上一层点颜色全为 0/1 的答案序列。
考虑一次对根节点的 dfs 的时间复杂度。
每访问一个点就会产生 O(m) 的代价，设 k 为 u 到根节点上的轻边条数，那么 u 被访问的次数为 2^k。可以证明访问次数总和是 O(n^{\log_23}) 的，在满二叉树下基本卡满。