自动搬运

查看原文

来自洛谷，原作者为

	Pig_Eat_Earth 这个人很菜，什么题都没A

搬运于2025-08-24 23:17:04，当前版本为作者最后更新于2025-05-31 12:22:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

记号与约定

• 题面中提到的，若无特殊说明，均与题面一致；
• $dp_u$：$S(T_u)$；
• $nl_u$：$T_u$ 所包含的叶子节点数；
• $pr_u$：$T_u$ 中 $\sum_{i=1}^{nl_u}f(i,nl_u)$；
• $sf_u$：$T_u$ 中 $\sum_{i=1}^{nl_u}f(1,i)$；

思路

一眼树形 DP。
在一棵子树 $T_u$ 中，类似 CDQ 分治地，我们可以把需要处理的 $[a,b]$ 分为三类：

1. 完全在左子树 $T_{A_u}$ 中的；
2. 完全在右子树 $T_{B_u}$ 中的；
3. 一部分在 $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}$。

时间复杂度

$O(n)$。

AC Code

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