方案数 / 距离统计
联合权值·括号树
本课摘要
方案数 / 距离统计课程回答“树上方案数与距离统计如何在合并时避免重复”。内容以联合权值·括号树为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。
- 判断方案数 / 距离统计的适用条件与状态边界
- 围绕“联合权值·括号树”推导转移与计算顺序
- 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节
正在整理目录…
从「求最优」转向「数东西」
前几类都在求极值（最大权、最小造价、最长链）。这一类换一副眼镜：统计—— 数满足某种条件的点对 / 路径 / 子串有多少、或它们的某个量之和是多少。转移里 常换成求和 或乘法。
先看一类清爽的：距离恰为 2 的点对统计。给树上每点一个权，要求所有距离为 2 的点对，其权乘积之和（以及最大乘积）。 直接两两枚举点对是 ， 不可行。关键观察一句话解决：
两点距离为 2，当且仅当它们有一个公共邻居（那个邻居是路径的中间点）。于是不枚举点对，改枚举中间点 ——m 的任意两个邻居就构成一个距离 2 点对。
O(度) 一次算完一个中间点
固定中间点 ，设它的邻居权为 。所有有序点对的乘积之和是：
这是一个恒等式：「和的平方」减去「平方和」，恰好去掉了 的对角项，剩下的正是所有 的交叉乘积。 只需扫一遍 m 的邻居累加 与 ， 就得到以 m 为中点的乘积和； 所有中间点加起来，总和是 。
最大乘积同理：维护 m 邻居里的最大与次大两个权， 即以 m 为中点的最大乘积；全局取最大。
本质
距离统计的通用招数是换枚举对象：不枚举「点对」而枚举「中间点 / 路径拐点」，把 的两两配对，压成每个点 的局部统计。配合「和的平方 − 平方和」这类恒等式，一次算完一个中心的全部贡献。这是树上「数点对」的核心思维。
跟着算一遍
小树：根 带 ； 的孩子 又带 。权 。逐个中间点统计：
点选中间点，看点对怎么冒出来
沿根链递推：括号树的 O(1) 计数
另一支是沿「根到点」的链递推方案计数。括号树：每个节点写着一个 或 ， 从根到某点的路径拼成一个括号串。要数出所有节点对应的根链里，合法括号子串的总数。
暴力对每个点重扫根链是 。妙处在于：设 = 「以 u 这个字符结尾的合法括号子串数」， 它能从父亲 O(1) 递推——若 是 且能与链上某个 配对（设那个 的前一位是 ），则
读作：以 u 结尾的合法子串 = 「以 p 结尾的合法子串」全部各自向右接上这对括号，再加「刚配好的这一对」本身。 用一个栈沿 DFS 维护未匹配的 ，进入子树时压栈 / 匹配，回溯时撤销。答案 = 。
常见陷阱：DFS 上的栈必须回溯撤销
括号树是在树上而非一条链上递推——从一个子树退回父亲、再进入另一个子树时，前一支压入栈的 必须弹出还原，否则会串味。标准写法是「进入时记下本层对栈的修改，递归返回后原样撤销」（可回滚栈）。另外 与答案都可能超 int，用 。
这两支——枚举中间点做距离统计与沿根链 O(1) 递推计数——覆盖了树上「数东西」的两大范式： 前者靠「换枚举对象 + 恒等式」摊平代价，后者靠「父到子的增量递推」避免重扫。它们和 覆盖 / 染色 里的方案计数一脉相承，只是把极值算子换成了求和 / 乘法。
例题
#include <iostream>
#include <vector>
using namespace std;
const int N = 200005;
const long long MOD = 10007;
vector<int> g[N];
long long w[N];
long long sumAns, maxAns;
void dfs(int u, int fa)
{
long long s1 = 0, s2 = 0; // 邻居权和、平方和
long long mx1 = 0, mx2 = 0; // 最大、次大邻居权
for (int v : g[u]) // ★邻居 = 所有相连点（父 + 孩子）
{
s1 = (s1 + w[v]) % MOD;
s2 = (s2 + w[v] * w[v]) % MOD;
if (w[v] > mx1) { mx2 = mx1; mx1 = w[v]; }
else if (w[v] > mx2) mx2 = w[v];
}
// 以 u 为中间点的所有距离 2 有序点对：乘积和 = (Σw)² − Σw²
sumAns = (sumAns + (s1 * s1 - s2) % MOD + MOD) % MOD;
maxAns = max(maxAns, mx1 * mx2); // 最大乘积 = 最大 × 次大
for (int v : g[u])
if (v != fa) dfs(v, u);
}
int main()
{
int n;
cin >> n;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; i++)
cin >> w[i];
dfs(1, 0);
cout << maxAns << " " << sumAns << endl;
return 0;
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int N = 500005;
vector<int> g[N];
string s; // 每个点上是 '(' 或 ')'
long long f[N]; // f[u]：以 u 结尾、向上到根方向的合法括号子串数
long long ans;
int stk[N], top; // 用栈匹配括号（栈存节点编号）
int match[N]; // match[u]：与 u 配对的那个 '(' 的父亲上一位
void dfs(int u, int fa)
{
int saved = -1; // 记录本层对栈的修改，回溯时撤销
if (s[u - 1] == '(') // '(' 入栈
{
stk[++top] = u;
// f[u] 继承父亲：新的 '(' 自身不能结尾合法串
f[u] = f[fa];
}
else // ')' 尝试与栈顶配对
{
if (top > 0)
{
int p = stk[top--]; // 弹出配对的 '('
saved = p;
// p 的父亲那条链上的 f + 本次新增的 1 个（p..u 这一对）
f[u] = f[/*p 的父亲*/ fa] + 1; // 示意：真实实现用 match 链递推
}
else
f[u] = 0;
}
ans += f[u]; // ★累加：每个点贡献「以它结尾的合法子串数」
for (int v : g[u])
if (v != fa) dfs(v, u);
if (s[u - 1] == '(') top--; // 撤销入栈
else if (saved != -1) stk[++top] = saved; // 撤销出栈
}
int main()
{
int n;
cin >> n >> s;
for (int i = 2; i <= n; i++)
{
int fa;
cin >> fa;
g[fa].push_back(i);
}
top = 0;
dfs(1, 0);
cout << ans << endl;
return 0;
}