T1
注意快读会把每行末尾的换行符读掉。
显然将关系转化成有向图，最后跑一遍拓扑看有没有环即可。考试的时候困的要死复杂度没算对，以为跑拓扑会T，所以为了骗分每加一条边就dfs搜一边，如果出了环就直接标记上。这样复杂度不太对，不过如果它环比较小可能会骗到点分。
当然数据比较水，就这么过了，还比tarjan判环跑得快挺多。
T2
n，q小于等于10000的只会(O(nq))爆扫一遍...听说只要用点技巧少扫几个就能骗到60分，反正我是不会。当然别用algorithm自带的那个max，手写、三目、if都行。
对于 (|a_i| leq 1) 的，把式子提一个(x)出来：
由于(a[i])只可能为-1， 0 ，1，显然后面的一次函数只有三种斜率。对于x<0，x>0分别按b最小最大考虑即可。
正解是维护凸包，单调栈或者二分都可以，但是我一个都不会。
于是有一种取巧的做法:
还是这个式子(f_{i}(x)=x(a_{i}x+b_i))
显然的是当x>=0时后面括号里的东西越大越好，当x<0时括号里的东西越小越好。
于是把询问都离线下来，对于x>=0和x<0的询问分别处理。
考虑x>=0怎么做，首先将x从小到大排序，同时将所有直线按b从大到小排序，对于一条直线，当他b小于前一条直线时，只有他的a大于前一条直线时这条直线才是有用的。
由于x从小到大排序了，所以后面的x取到最优值的直线一定在排在前面的x取到最优值的那条直线的后面，所以可以维护一个指针，对于每个x从指针往后扫一遍有用的直线，如果能取到最优值就更新指针位置及答案。
int pos = 1;
for (register int i = 1; i <= n1; ++i) {
x = x1[i].v;
for (register int j = pos; j <= m; ++j) {
if (a[j] * x * x + b[j] * x >= ans[x1[i].id])
ans[x1[i].id] = a[j] * x * x + b[j] * x, pos = j;
}
}
x<0时同理去做即可。
显然当所有x的最优值都在前几条直线上取到时这种做法会被卡掉，因为每次为了保证正确性都会把后面的所有直线扫一遍，但是数据没有那么强，配合上面(|a_i| leq 1)的特判即可水过本题。
T3
前两个点只会大概为(O(n^{max a_i}))的爆搜，但是考场上挂了，还没改。
n=2的式子不会推，弱哭了...
对于N=2的情况，可以分为两种来考虑：a2没被取完，a2被取完了。
-
对于(a_2)没被取完的情况：
对答案的贡献就是：(sumlimits_{i=0}^{a_2-1}((a_1 + i) imes frac{C_{a_1+i-1}^{i}}{2^{a_1+i}}))
对于(frac{C_{a_1+i-1}^{i}}{2^{a_1+i}})我的理解可能不够准确，我的理解就是这种选法的方案数比上总的方案数，即概率。组合数那里减一的原因是保证最后一个选的是(a_1)。 -
对于(a_2)取完的情况：
贡献也是次数乘上概率，此时直接用1减去前一种情况的概率和即为所需概率。
形式化一点：((a_1 + a_2) imes (1-sumlimits_{i=0}^{a_2-1}frac{C_{a_1+i-1}^{i}}{2^{a_1+i}})) -
总的就是：(ans=a_1 + sumlimits_{i=0}^{a_2 - 1}frac{i imes C_{a_1+i-1}^{i}}{2^{a_1+i}} + a_2 imes (1-sumlimits_{i=0}^{a_2-1}frac{C_{a_1+i-1}^{i}}{2^{a_1+i}}))
考虑正解，我们的最终需求只有(a_1)，所以对于别的(a)，他们是不会相互影响的，也就是说，我们不关心他们之间的相对关系，也不关心每个(a)最终会是多少，而只关心每个(a)与(a_1)之间的关系是怎样的。
怎么解释能更明白一点...让我再想想...
根据期望的线性性以及上述，(N=2)的做法是普适的。
所以定义一个函数(f_{a}=sumlimits_{i=0}^{a-1}frac{i imes C_{a_1+i-1}^{i}}{2^{a_1+i}} + a imes (1-sumlimits_{i=0}^{a-1}frac{C_{a_1+i-1}^{i}}{2^{a_1+i}}))
含义是在当前的(a_1)下，(a_i)的贡献的期望，也就是每个(a_i)被取的期望次数。
这个函数可以(O(1))的转移，于是可以预处理一下。
答案即为：(a_1 + sumlimits_{i = 2}^{n}f_{a_i})
T4
1跟8的点树剖之后直接暴力跳父亲就能做吧，大概...还没改到这。
a[i]<2的点的话...
a[i]=0时答案就是距离，不会有变化。当a[i]=1时，如果他到一个点的距离为偶数，a[i]会使贡献+1，对每个a[i]=1的点预处理到一个祖先的路径上距离为偶数的点的个数，用倍增实现应该、大概、也许是行的...
抱歉口胡的，不要在意。