专栏文章

【P12645 [KOI 2024 R1] 二叉树】题解

PPig_Eat_Earth
P12645题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip62vol
此快照首次捕获于
2025/12/03 06:45
3 个月前
此快照最后确认于
2025/12/03 06:45
3 个月前
查看原文

记号与约定

  • 题面中提到的，若无特殊说明，均与题面一致；
  • dpudp_u：S(Tu)S(T_u)；
  • nlunl_u：TuT_u 所包含的叶子节点数；
  • prupr_u：TuT_u 中 ∑i=1nluf(i,nlu)\sum_{i=1}^{nl_u}f(i,nl_u)；
  • sfusf_u：TuT_u 中 ∑i=1nluf(1,i)\sum_{i=1}^{nl_u}f(1,i)；

思路

一眼树形 DP。
在一棵子树 TuT_u 中，类似 CDQ 分治地，我们可以把需要处理的 [a,b][a,b] 分为三类：
  1. 完全在左子树 TAuT_{A_u} 中的；
  2. 完全在右子树 TBuT_{B_u} 中的；
  3. 一部分在 TAuT_{A_u} 中，一部分在 TBuT_{B_u} 中的。
前两种情况在 TAuT_{A_u} 和 TBuT_{B_u} 中已经处理过了，因此只需要处理第三种。
观察发现，在第三种情况中，除了 [1,nlu][1,nl_u] 外，剩下的都满足 f(a,b)=f(a,nlAu)+f(nlAu+1,b)f(a,b)=f(a,nl_{A_u})+f(nl_{A_u}+1,b)，即左子树中的 ff 后缀和加上右子树中的 ff 前缀和。
以下令 li=f(i,nlAu),ri=f(nlAu+1,nlAu+i),n=nlAu,m=nlBu,∑l=∑i=1nli=sfAu,∑r=∑i=1mri=prBul_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}
于是我们能够得到： dpu=dpAu+dpBu+∑i=2n∑j=1m(li+rj)+∑i=1m−1(l1+ri)+f(1,nlu)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) 现在的问题在于如何快速计算后面三项。
注意到 l1=rm=f(1,nlu)=1l_1=r_m=f(1,nl_u)=1，于是有：
后三项=∑i=2n(m×li+∑r)+(m−1)l1+∑i=1m−1ri+1=m∑i=2nli+(n−1)∑r+∑i=1m−1ri+m=m(∑l−1)+(n−1)∑r+(∑r−1)+m=m∑l+n∑r−1=m×sfAu+n×prBu−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,sfpr,sf 推出 pru,sfupr_u,sf_u。
先看 prpr。注意到 ∑i=1nf(1,i)=prAu,f(1,nlu)=1\sum_{i=1}^nf(1,i)=pr_{A_u},f(1,nl_u)=1，则只需考虑 (n,nlu)(n,nl_u) 范围内的叶子节点。我们发现这些叶子节点的前缀 ff 其实就是其在 TBuT_{B_u} 的前缀 ff 再加上一整颗左子树。于是有： pru=prAu+(prBu−1)+(nlBu−1)+1=prAu+prBu+nlBu−1pr_u=pr_{A_u}+(pr_{B_u}-1)+(nl_{B_u}-1)+1=pr_{A_u}+pr_{B_u}+nl_{B_u}-1 同理： sfu=sfAu+sfBu+nlAu−1sf_u=sf_{A_u}+sf_{B_u}+nl_{A_u}-1
剩下的信息就很好求了。
初始化 dp0=nl0=pr0=sf0=1dp_0=nl_0=pr_0=sf_0=1。
同时nlu=nlAu+nlBunl_u=nl_{A_u}+nl_{B_u}。

时间复杂度

O(n)O(n)。

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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...