T1
我们容易想到，为了让答案字符串字典序尽可能小，我们要让尽可能小的字母加到答案串前面。
我们枚举答案串的每一位进行处理，每一次找原串中可以加进来的最小的字母将其加入答案串。每加一个字符的代价是原串中在它之前未被加入答案串的字符的个数，这个可以使用树状数组来维护一下。
T2
每一个点的高度正好等于点的编号。
我们定义 (dp_i) 为以 (i) 为结尾的上升序列有几个。
我们得到转移式 ： dp[v] += dp[u]+1 (u < v)
T3
我们发现这道题 (n^2) 可过……然后本来准备的暴力变成了正解qwq，然后因为懒得离线就炸了空间英勇爆零。
我们将询问离线，降低空间复杂度。
我们使用bfs求出长度为奇数和偶数的最短路，使用拆点实现