P3060 [USACO12NOV]Balanced Trees G 题解
ppip
·
·
题解
题目传送门
对于点 $i$，如果 $i$ 上是左括号，我们令 $a_i=1$，否则 $a_i=-1$。
先考虑序列上选子串的问题。
现在，设 $f_n$ 表示 $\sum_{i=1}^na_i$。很明显，区间 $[a,b]$ 是合法的，当且仅当 $f_{a-1}=f_b=\min\{f_x|x\in [a-1,b]\}$。次数，答案为 $\max\{f_x|x\in[a,b]\}-f_{a-1}$。
我们枚举 $x$ 计算贡献。对于每个下标 $x$，我们想要找到它在一个合法子串中能达到的最大答案。有一个结论：首先令 $g=\max(\min\{f_y|y\in[0,z)\}, \min\{f_y|y\in[z,n]\})$，其中 $f_0=0$。一定存在一对 $a,b$ 使得 $g=f_a=f_b=\min\{f_y|y\in[a,b]\}$，那么 $x$ 贡献的答案就是 $f_x-g$。注意此处对应的合法串为 $(a,b]$。具体来说，$a$ 是 $x$ 左边离它最近的 $f_a=g$，$b$ 则是右边最近的。
因为 $f$ 相邻两项差的绝对值为 $1$，所以左右两侧一定都包含这个值（在上面的表达式里，$x$ 一侧的最小值 $ < g$ 由于变化量为 $1$，$z$ 和最小值中间一定经过 $g$）。同时 $[a,b]$ 中不可能有 $<g$ 的值，否则在达到这个更小的值之前，一定会先遇到 $g$。于是我们就证明了结论。
为了在树上做这个问题，我们进行一个转化：对于一个点 $x$，它的贡献为它结尾的一个子串的最大权值和，和它下一个数开头的一个子串的最小权值和的相反数，取更小的那个。证明类似上面。这里的值指 $a$。
搬到树上就是，我们枚举一个点和它的下一个点（即，记无向边为两条有向边，然后枚举每条边），设为 $u,v$，答案就是 $u$ 开头的不经过 $v$ 的、点权和最大的一条路径，和 $v$ 开头的不经过 $u$ 的、边权和最小的一条路径的相反数，这两个取较小值。
现在问题转化为了，求每个点不经过相邻的另外一个点的权值和最大/最小路径。这个可以换根 DP 求。
时空复杂度均为 $\Theta(n)$，十分优秀。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define all(awa) awa.begin(),awa.end()
constexpr int N{40000};
// 后缀：[m]最大值，[n]最小值，前缀：[f]子树内，[g]子树外
int fm[N+5],fn[N+5],gm[N+5],gn[N+5],fa[N+5],a[N+5];
vector<int> e[N+5];
void solve(int u) {
for (auto v:e[u]) {
solve(v);
fm[u]=max(fm[u],fm[v]);
fn[u]=min(fn[u],fn[v]);
}
fm[u]+=a[u];fn[u]+=a[u];
}
void sulve(int u) {
gm[u]+=a[u];gn[u]+=a[u];
for (auto v:e[u]) gm[v]=max(a[u],gm[u]),gn[v]=min(a[u],gn[u]);
if (e[u].size()>1) {
int mx{0},mt{0},mn{0},mp{0};
for (auto v:e[u]) {
if (fm[v]>mx) mt=mx,mx=fm[v];
else mt=max(mt,fm[v]);
if (fn[v]<mn) mp=mn,mn=fn[v];
else mp=min(mp,fn[v]);
}
for (auto v:e[u]) {
gm[v]=max(gm[v],(fm[v]==mx?mt:mx)+a[u]);
gn[v]=min(gn[v],(fn[v]==mn?mp:mn)+a[u]);
}
}
for (auto v:e[u]) sulve(v);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;cin>>n;
for (int i{2};i<=n;++i) {
cin>>fa[i];
e[fa[i]].push_back(i);
}
for (int i{1};i<=n;++i) {
char c;while (isspace(c=getchar()));
a[i]=(c=='('?1:-1);
}
solve(1);
sulve(1);
int ans{0};
for (int i{2};i<=n;++i) ans=max({ans,min(fm[i],a[i]-gn[i]),min(-fn[i],gm[i]-a[i])});
cout<<ans<<endl;
return 0;
}
```