复盘
T1 好像很可做。推式子启动。1h 过了大样例。
T2。怎么又是组合数，比普通的范德蒙德卷积多一个上限？这可做吗？好像不会，部分分启动。
有 \(45\) 分暴力。两个简单的性质能做到 \(55\) 分。但 \(n-m\le 20\) 真的没有思路。事实上这个东西非常好做（观察组合数什么是否为 \(0\)）但是没想到。
T3。\(\mathcal O(n^2)\) 好像非常简单。直接开写！
……？复杂度好像算错了，是三次方的。重新想。
发现还是很简单。很快写完了。
赛后发现这个做法是能通过 \(t\) 全部相同的。但是没写。
预计 \(100+55+30+0\)，然后 T3 没开 long long 炸了 \(20\)。
总结
好的：
- T1 做对了。但好像比正解复杂，但是积累了一个方案数转期望再转方案数的 trick。
不足：
- long long
- 最后时间太紧张，T3 是可以拿 \(45\) 分的（如果开了 long long）
- T2 没做出来。感觉头脑清醒的话做出来问题不大。
知识点
T1：基环树，数学
T2：数学
T3：树形 DP，换根 DP
题解
A. 强连通分量
赛时写的打草用的，发现可以直接当总结的题解。
考虑一颗基环树的答案。
环上有 \(a\) 个点，环外有 \(b\) 个点。
枚举总共删 \(x\) 个点。
如果全删环外，scc 数量为 \(b+1-x\)。
如果删 \(i\) 个环内，scc 数量为 \(b+b-x\)。
所以要求的是：
\[\sum_x\left( (b+1-x) \dbinom bx + \sum_{i=1}^a \dbinom ai \dbinom b{x-i} (a+b-x)\right) \]怎么快速求：
\[\sum_{i=1}^a\dbinom ai \dbinom b{x-i} \]范德蒙德卷积！
组合意义是，总共选 \(x\) 个物品，从 \(a\) 中选 \(i\) 个，从 \(b\) 中选 \(x-i\) 个，\(i \ge 1\)，方案数。
可以看作从 \(a+b\) 中选 \(x\) 的方案数，减去从 \(b\) 中选 \(x\) 的方案数。
\[\dbinom {a+b}x-\dbinom bx \]怎么合并两颗子树的答案？
转成期望。然后直接线性性相加。
\[(\dfrac a{2^A}+\dfrac b{2^B}) \times 2^{A+B} \]B. 《原神》
快进到求：
\[\sum_{i=0}^{n} f(i)\dbinom xi\dbinom {m-x}{n-i} \]其中 \(f(i) = 2 \operatorname{highbit}(i+1)\)。
注意到对于 \(i \in [2^{j-1}-1,2^j-2]\)，都有 \(f(i)=2j\)，因此可以分成 \(\log\) 个段，分别计算。
为了方便记 \(l_j = 2^{j-1}-1,r_j = 2^j-2\)。
\[\sum_{j=1}^{30} 2j \times\sum_{i=l_j}^{r_j}\dbinom xi \dbinom {m-x}{n-i} \]考虑如何快速计算 \(g(x,k)=\sum\limits_{i=0}^k\dbinom xi \dbinom {m-x}{n-i}\)。那么上式的后半部分就是 \(g(x,r_j)-g(x,l_j-1)\)。
考虑其组合意义：
- 有 \(m\) 个物品，要选 \(n\) 个，且前 \(x\) 个中选择的物品 \(\le k\) 个。
一个事实是当 \(k \ge x\) 时 \(g(k,x)=\dbinom mn\)。
考虑 \(g(k,x) \to g(k,x+1)\) 的增量，或者说 DP 转移。
注意到只有一种方案是不合法且被转移过去的，即 第 \(x+1\) 个物品选，且前 \(x\) 个物品中选了 \(k\) 个。这种情况的方案数是 \(\dbinom xk \dbinom {m-x-1}{n-k-1}\)。所以：
\[g(k,x+1) = g(k,x)-\dbinom xk \dbinom {m-x-1}{n-k-1} \]C. 叶子
首先每个叶子最终走到的有效计分点，一定是 \(s \rightsquigarrow t\) 路径的一段前缀。不妨二分这个点 \(mid\)。然后需要 check：
- 所有能到达 \(mid\) 的叶子节点中，\(s \rightsquigarrow t\) 是否是长度最短的。
不妨将 \(t\) 设为根。那么能到达 \(mid\) 的叶子节点，等价于 \(mid\) 的子树内的叶子节点。
于是对于每次询问给定的 \(t\) 都做一遍这样的树形 DP。复杂度 \(n|\{t_{1\sim q}\}|\)。有 \(45\) 分。
考虑优化。我们把 \(s \rightsquigarrow t\) 的路径画出来：
当以 \(t\) 为根时，\(v_1\) 的子树仍是原始的子树，而 \(v_2\) 的子树全部取了反。于是换根 DP。
标签：11.25,dbinom,sum,中选,mid,long,模拟,DP From： https://www.cnblogs.com/2huk/p/18568749