树形dp+构造+期望+停时定理+cdq分治
A.路哥
首先我们可以求出所有权值为 \(k\) 的方案数总和,再除以 \(2^{n-1}\) 就是总期望。
可以树形dp,设 \(f[i][j]\) 表示当前考虑到 \(i\) 点,所拿的总和为 \(j\) 的方案数。
这样设状态,是按照 \(dfs\) 序进行推进的,所以每次处理儿子的时候要继承父亲的方案数。
每次回溯时,要把贡献统计到父亲上面,同时也要考虑不走这条边的方案数。
B.密电
设给出数组为 \(\{b_n\}\)。
那么排完序后,一定有:\(b_1=a_1+a_2,b_2=a_1+a_3\),不确定的只只有 \(a_2+a_3\) 和后面的关系。
这时候就可以枚举 \(a_2+a_3\) 的位置,这样就求出了 \(a_1,a_2,a_3\),并且剩下的最小的一定是 \(a_1+a_4\)。
那么知道 \(a_4\) 后,就可以删除 \(a_2+a_4,a_3+a_4\),这样剩下的就是 \(a_1+a_5\) 了,归纳就能求出答案。
C.战争
停时定理和鞅,不会。
D.送信
cdq好题。
我们观察到,给定的路径如果想产生贡献,那么询问的两个端点一定在它的子树里。
这里的"子树",是指连接这两个点的极大互斥连通块。
可以通过 \(dfs\) 序对此加以限制,设询问的两个路径为 \(x_i,y_i\),其中路径 \(x_j\rightarrow y_j\) 若能够产生贡献,则需满足:
\[\begin{cases} dfn[x_i]\in[l,r]\\dfn[y_i]\in[L,R]\\t_i>t_j \end{cases} \]其中 \([l,r],[L,R]\) 的范围可以根据 \(x_j,y_j\) 的形态来讨论,这里可以画图理解。
之后这就是一个典型的三维偏序,直接上 cdq 就好了。
trick:cdq时要查 \(x\in[l,r]\and\ y\in[L,R]\) 的数对 \((x,y)\) 的数量,但因为第二维限制用双指针维护,不好统计。可以差分后统计 \([1,l-1]\) 和 \([1,r]\) 的即可。
另外 \(y\in[L,R]\) 这一限制也可以差分后树状数组,而避免线段树。