Tourism
容易想到跑出dfs树，这样只有返祖边，且每个点的深度不超过\(10\)。
考虑状压祖先的状态，设\(f_{i,S}\)表示dfs到了\(i\)点，祖先的状态为\(S\)的最小值。
\(S\)的每一位由三种组成：\(0\)没选，且没有儿子覆盖，\(1\)选了，\(2\)没选但是有儿子覆盖。
既要从父亲拿到状态又要从儿子返回状态，所以放到dfs序上比较好写，时间复杂度\(O(n3^{10})\)
Freight
我是sb。
显然序列会被分成若干段，每段内的火车先全部过去再全部回来。
设\(f_i\)表示\(i\)为某段结尾的最小时间，容易有\(O(n^2)\)的转移：\(f_i=\min\limits_{j=1}^{i} \max(A_i,f_{j-1}+i-j+1)+2(s-1)+i-j+1\)。
然后\(\max\)里面的东西一个是单调递增，一个是单调递减的，双指针找到分界点就可以\(O(1)\)转移。
FarmCraft
设\(f_i\)表示\(i\)子树内的最小时间，只需要考虑两颗子树到底谁放前面。设两个子树\(i,j\)的大小分别为\(s_i,s_j\)。
\(i\)放前面的代价为\(\max(f_i,f_j+2s_i)+1\)
\(j\)放前面的代价为\(\max(f_j,f_i+2s_j)+1\)。
因为\(f_i+2s_j+1>f_i\)，故可写成\(f_j+2s_i<f_i+2s_j\)，即\(2s_i-f_i<2s_j-f_j\)。按照这个东西排序即可。
时间复杂度\(O(n\log n)\)
Salad Bar
带log的是啥玩意儿。
将p看作\(1\)，\(j\)看成\(-1\)，前缀和为\(Sum_i\)，则满足条件的区间\([l,r]\)相当于对于所有\(l\leq i\leq r\)，使得\(Sum_{l-1}\leq Sum_i\leq Sum_{r}\)。
先单调栈处理出每个点\(i\)左边最近的大于它的点，记为\(j\)，则最优的左端点为\((j,i]\)区间的最左边的最小值所在的位置。
最小值显然是满足条件的，因为它在最左边所以更左边的左端点显然不满足条件。所以这个是最优的。
如果你被诈骗去写st表就上当了，这个东西在单调栈的时候记单调栈内每个点和上面一个点区间内的最小值，就可以做到\(O(n)\)。写起来极度舒适。
标签：submission,2s,max,Sum,POI2014,leq,单调 From： https://www.cnblogs.com/275307894a/p/17025088.html