P9655 [GROI-R2] Beside You

, ,

Description

题目很长，超级差评。

给定一颗括号树（即每个点都有一个括号）。

要求找到一个树上的最大子结构，使得这个子结构连通，且从这个结构的根（即选择的子结构在原树高度最低的节点）出发到达每一个叶子结点（除根之外所有度数不超过 $1$ 的节点）的链构成的括号序列合法。

$n\le 5\times 10^5$

Solution

这道题目 $O(n)$ 的长剖真是很妙啊。在算法实现上也是。

经典套路把一个左括号变成 $1$，右括号变成 $-1$，那么一个序列是合法的充要条件就是总和为 $0$，所有前缀和的值都 $\ge 0$。

但是这样在本题不太好啊，如果考虑 dp 的话就要想从子树合并过来。所以在这题中，可以把右括号变成 $1$，左括号变成 $-1$，每次转移的时候强制保证后缀和保证 $\ge 0$。这样就很自然的设出 $f_{x,i}$ 表示在 $x$ 的子树中，后缀和为 $i$ 的最大的能选的数。

我们需要维护 $f_{x,i+a_x}\gets \sum f_{y,i}$，还要将 $f_{x,i}$ 中有值的数 $+1$，也就是把 $x$ 不作为叶子节点选进去。

这样直接做是 $O(n^2)$ 的。

我们观察到第二维的范围最大为深度，且每次最多左右移动一位。这就与长剖优化 dp 的经典场景，第二维下标为深度很像啊！

想到这里，合并是平凡的，但还有一个关键在于，将 $f_{x,i}>0$ 的地方 $+1$。考虑打上标记 $t_{x,i}$ 表示 $f_{x,j\ge i}$ 的部分 $+t_{x,i}$。我们可以以类似于懒惰标记的形式，要用到了就把标记暴力打到 $f$ 上去，$t$ 往后推，否则接着合并上去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 2000005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int a[maxn];
int buff[maxn*2],*f[maxn],*fp=buff;
int bt[maxn*2],*t[maxn],*tp=bt;
int deep[maxn],son[maxn],top[maxn];
vector<int>to[maxn];
void dfs1(int x,int pre) {
	deep[x]=1;
	for (auto y:to[x]) if (y^pre) {
		dfs1(y,x);
		deep[x]=max(deep[x],deep[y]+1);
		if (deep[x]==deep[y]+1) son[x]=y;
	}
}
int ans,n;
void update(int x,int p) {
	p=min(deep[x],p);
	int s=0,i;
	for (i=top[x];i<=p;i++) {
		s+=t[x][i];
		if (f[x][i]) f[x][i]+=s;
		t[x][i]=0;
	}
	if (p+1<=deep[x]) t[x][p+1]+=s;
	top[x]=p+1; 
}
void dfs2(int x,int pre) {
	int i;
	if (son[x]) {
		int y=son[x],i;
		f[y]=f[x]+a[x];
		t[y]=t[x]+a[x];
		dfs2(y,x);
		if (a[x]==-1) {//不能转移 -1。
			update(son[x],1);
			f[y][0]=0;
		}
	}
	for (auto y:to[x]) if (y!=son[x]&&y!=pre) {
		f[y]=fp+deep[y]+2,fp+=deep[y]*2+4;
		t[y]=tp+deep[y]+2,tp+=deep[y]*2+4;
		dfs2(y,x);
		update(y,deep[y]);
		update(x,deep[y]+1);
		if (a[x]==1) {
			for (i=0;i<=deep[y];i++) f[x][i+1]+=f[y][i];
		} 
		else {
			for (i=1;i<=deep[y];i++) f[x][i-1]+=f[y][i];
		} 
	}
	if (a[x]==1&&!f[x][1]) {
		update(x,1);
		f[x][1]=1;
		if (f[x][0]) f[x][0]++;
		if (deep[x]>=2) t[x][2]++,top[x]=0;
	}
	else t[x][0]++,top[x]=0;
	if (f[x][0]) ans=max(ans,f[x][0]+t[x][0]);
}
signed main(void){
	int i,x,y;char ch;
	read(n);
	for (cin>>ch,i=1;i<=n;i++) {
		if (ch==')') a[i]=1;
		else a[i]=-1;
		ch=getchar();
	}
	for (i=1;i<n;i++) {
		read(x),read(y);
		to[x].push_back(y);
		to[y].push_back(x);
	}
	dfs1(1,0);
	f[1]=fp+deep[1]+2,fp+=deep[1]*2+4;
	t[1]=tp+deep[1]+2,tp+=deep[1]*2+4;
	dfs2(1,0);
	printf("%d\n",ans);
	return 0;
}

现在来分析推标记的复杂度。可以类似于长剖合并的复杂度那样。观察到每个点在非合并的阶段推标记的次数都是 $O(1)$ 的。而在合并的时候，链上的每个点又最多会遍历一次。每条链只有在最顶端的时候会被合并一次。所以是 $O(n)$ 的。就是常数有点小大。