[是男人就过8题——Pony.ai]Perfect N-P Arrays
题目大意：
一棵\(n(\sum n\le5\times10^6)\)个结点的树，每个结点都有一个括号。求树上一个合法的括号序列使得若将'('当成\(1\)，')'当成\(-1\)。该序列最大前缀和最大，输出最大前缀和。
思路：
由于括号序列前缀和是连续的，所以我们可以把括号序列任意时刻前缀和\(\ge 0\)的限制给去掉。两遍树形DP求出从一个点出发最大/最小前缀和。绝对值取\(\min\)后即为经过这个点的最大答案。注意到最大/最小前缀和可能来自于同一棵子树，因此我们还需记录次大/次小值。
源代码：
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) neg|=ch=='-';
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return neg?-x:x;
}
const int N=1e6+1;
std::vector<int> e[N];
int w[N],ans,max[N][2],min[N][2];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
inline void upd1(const int &x,const int &y) {
int tmp1=min[y][0]+w[x];
int tmp2=max[y][0]+w[x];
for(register int i=0;i<2;i++) {
if(tmp1<min[x][i]) {
std::swap(tmp1,min[x][i]);
}
if(tmp2>max[x][i]) {
std::swap(tmp2,max[x][i]);
}
}
}
inline void upd2(const int &x,const int &y) {
int tmp1=min[y][min[y][0]==min[x][0]+w[y]];
int tmp2=max[y][max[y][0]==max[x][0]+w[y]];
if(tmp1!=INT_MAX) tmp1+=w[x];
if(tmp2!=INT_MIN) tmp2+=w[x];
for(register int i=0;i<2;i++) {
if(tmp1!=INT_MAX&&tmp1<min[x][i]) {
std::swap(tmp1,min[x][i]);
}
if(tmp2!=INT_MIN&&tmp2>max[x][i]) {
std::swap(tmp2,max[x][i]);
}
}
}
void dfs1(const int &x,const int &par) {
max[x][0]=min[x][0]=w[x];
max[x][1]=INT_MIN;
min[x][1]=INT_MAX;
for(auto &y:e[x]) {
if(y==par) continue;
dfs1(y,x);
upd1(x,y);
}
}
void dfs2(const int &x,const int &par) {
for(auto &y:e[x]) {
if(y==par) continue;
ans=std::max(ans,std::min(std::abs(max[y][0]),std::abs(min[x][min[x][0]==min[y][0]+w[x]])));
ans=std::max(ans,std::min(std::abs(min[y][0]),std::abs(max[x][max[x][0]==max[y][0]+w[x]])));
upd2(y,x);
dfs2(y,x);
}
}
int main() {
int n;
while(~scanf("%d",&n)) {
for(register int i=1;i<=n;i++) {
const int p=getint();
if(p) add_edge(p,i);
w[i]=getint();
}
dfs1(1,0);
dfs2(1,0);
printf("%d\n",ans);
for(register int i=1;i<=n;i++) {
e[i].clear();
}
ans=0;
}
return 0;
}