【P12645 [KOI 2024 R1] 二叉树】题解
Pig_Eat_Earth
·
·
题解
记号与约定
- 题面中提到的，若无特殊说明，均与题面一致；
-
-
-
-
## 思路
一眼**树形 DP**。
在一棵子树 $T_u$ 中，类似 **CDQ 分治**地，我们可以把需要处理的 $[a,b]$ 分为三类：
- 完全在左子树 T_{A_u} 中的；
- 完全在右子树 T_{B_u} 中的；
- 一部分在 T_{A_u} 中，一部分在 T_{B_u} 中的。
前两种情况在 T_{A_u} 和 T_{B_u} 中已经处理过了，因此只需要处理第三种。
观察发现，在第三种情况中，除了 [1,nl_u] 外，剩下的都满足 f(a,b)=f(a,nl_{A_u})+f(nl_{A_u}+1,b)，即左子树中的 f 后缀和加上右子树中的 f 前缀和。
以下令 l_i=f(i,nl_{A_u}),r_i=f(nl_{A_u}+1,nl_{A_u}+i),n=nl_{A_u},m=nl_{B_u},\sum l=\sum_{i=1}^nl_i=sf_{A_u},\sum r=\sum_{i=1}^mr_i=pr_{B_u}
于是我们能够得到：
dp_u=dp_{A_u}+dp_{B_u}+\sum_{i=2}^n\sum_{j=1}^m(l_i+r_j)+\sum_{i=1}^{m-1}(l_1+r_i)+f(1,nl_u)
现在的问题在于如何快速计算后面三项。
注意到 l_1=r_m=f(1,nl_u)=1，于是有：
\begin{aligned}
\text{后三项}&=\sum_{i=2}^n(m\times l_i+\sum r)+(m-1)l_1+\sum_{i=1}^{m-1}r_i+1 \\
&=m\sum_{i=2}^nl_i+(n-1)\sum r+\sum_{i=1}^{m-1}r_i+m \\
&=m(\sum l-1)+(n-1)\sum r+(\sum r-1)+m \\
&=m\sum l+n\sum r-1 \\
&=m\times sf_{A_u}+n\times pr_{B_u}-1
\end{aligned}
接下来的问题就是如何通过左右子树的 pr,sf 推出 pr_u,sf_u。
先看 pr。注意到 \sum_{i=1}^nf(1,i)=pr_{A_u},f(1,nl_u)=1，则只需考虑 (n,nl_u) 范围内的叶子节点。我们发现这些叶子节点的前缀 f 其实就是其在 T_{B_u} 的前缀 f 再加上一整颗左子树。于是有：
pr_u=pr_{A_u}+(pr_{B_u}-1)+(nl_{B_u}-1)+1=pr_{A_u}+pr_{B_u}+nl_{B_u}-1
同理：
sf_u=sf_{A_u}+sf_{B_u}+nl_{A_u}-1
剩下的信息就很好求了。
初始化 dp_0=nl_0=pr_0=sf_0=1。
同时nl_u=nl_{A_u}+nl_{B_u}。
时间复杂度
## AC Code
```cpp
#include <bits/stdc++.h>
#define UP(i, l, r) for(int i = (l); i <= (r); ++ i)
#define DN(i, l, r) for(int i = (r); i >= (l); -- i)
#define LUP(i, l, r) for(ll i = (l); i <= (r); ++ i)
#define LDN(i, l, r) for(ll i = (r); i >= (l); -- i)
#define FE(i, s) for(auto i : s)
#define PB push_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int INF = 0x3f3f3f3f, INFB = 0x3f, N = 1e5, MOD = 1e9 + 7;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
int n, a[N + 5], b[N + 5];
ll dp[N + 5], nl[N + 5], sf[N + 5], pr[N + 5];
bitset<N + 5> ir, vis;
ll md(ll x){ return (x % MOD + MOD) % MOD; }
void dfs(int u){
if(!vis[a[u]]){
dfs(a[u]);
vis.set(a[u]);
}
if(!vis[b[u]]){
dfs(b[u]);
vis.set(b[u]);
}
nl[u] = md(nl[a[u]] + nl[b[u]]);
sf[u] = md(md(sf[a[u]] + nl[a[u]]) + sf[b[u]] - 1);
pr[u] = md(md(pr[b[u]] + nl[b[u]]) + pr[a[u]] - 1);
dp[u] = md(md(md(dp[a[u]] + dp[b[u]]) + md(nl[b[u]] * sf[a[u]])) + md(md(nl[a[u]] * pr[b[u]]) - 1));
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
dp[0] = nl[0] = sf[0] = pr[0] = 1;
ir.set();
vis.set(0);
UP(i, 1, n){
cin >> a[i] >> b[i];
ir.reset(a[i]);
ir.reset(b[i]);
}
UP(i, 1, n) if(ir[i]) dfs(i);
UP(i, 1, n) cout << dp[i] << endl;
}
```