BZOJ 3681 Arietta（主席树+网络流）

发表于 |
字数统计: 1,674字 | 阅读时长 ≈ 8min

Arietta

问题描述

Arietta 的命运与她的妹妹不同,在她的妹妹已经走进学院的时候,她仍然留在山村中。

但是她从未停止过和恋人 Velding 的书信往来。一天,她准备去探访他。

对着窗外的阳光,临行前她再次弹起了琴。

她的琴的发声十分特殊。

让我们给一个形式化的定义吧。

所有的 $n$ 个音符形成一棵由音符 $C$ ( 1 号节点) 构成的有根树,每一个音符有一个音高$ H_i$ 。

Arietta 有 $m$ 个力度,第 $i$ 个力度能弹出 $D_i$ 节点的子树中,音高在$ [L_i,R_i]$ 中的任意一个音符。

为了乐曲的和谐,Arietta 最多会弹奏第 $i$ 个力度 $T_i$ 次。

Arietta 想知道她最多能弹出多少个音符。

输入格式

输入共 m + 3 行。

第一行两个整数 n, m ,意义如题目所述。

第二行 n - 1 个整数 $P_i$ ,表示节点$ i ( i = 2 . . . n ) $的父亲节点的编号。

第三行 n 个整数 $H_i$ 。

接下来的 m 行,每行四个整数 $L_i,R_i,D,T_i$

输出格式

输出一个整数表示 Arietta 最多能弹奏多少音符。

样例输入

5 2

1 1 2 2

5 3 2 4 1

1 3 2 1

3 5 1 4

样例输出

4

数据范围与约定

对于 100% 的数据,$1 ≤ n, m ≤ 10000$ 。

对于所有数据$1<=H_i,T_i,P_i<=N,1<=L_i<=R_i<=N$

这个题容易发现就是一个简单的网络流，每次向子树中权值在$[L_i,R_i]$中的点连边，然后每个点只能用一次，求一个最大流。但是直接上边数的规模是$O(n^2)$级别的。肯定是不行的。

考虑优化，由于要求子树中权值在$[L_i,R_i]$中的点，启发我们想到建立线段树，然后进一步的考虑主席树。

我们在每个节点维护一颗主席树，这颗主席树的叶子节点连到该点子树中的对应权值的点，然后这样向$[L_i,R_i]$连边就只需要在主席树上向对应区间的点连边了，这样的边最多有$\log n$条。然后主席树上每个点往上一个版本对应点连边，同时向新建的儿子连边.

但是需要考虑如何得到每个点的主席树，这里考虑用轻重链剖分的思想，每个点的主席树直接继承重儿子的，然后将其他轻儿子子树中的点暴力插入进去。

考虑这样的时间复杂度，由于每个点往上最多经过$\log n$条重链，因此每个点最多被暴力添加$\log n$次。因此时空复杂度都是$O(n\log^2 n)$，容易发现边的规模也是$O(n\log^2n)$的。

但是还需要注意一个问题，就是每次构建主席树的时候，可以打一个时间标记，标记每个点是何时被新建的，如果当前在主席树中访问到的点已经是这次构建中新建的点了，就不用再新建节点了。能够少添加很多节点和边，省下时间和空间。

这样做实测空间消耗是$23M$左右，另外疑似这题基础的SAP过不了，需要bfs预处理来优化。

另外，这题也可以用线段树合并做，思路差不多，每次直接将儿子节点的线段树拿来合并得到当前节点的线段树即可。复杂度是一样的，但是需要注意细节，实现的好的话空间能到$20M$以下，时间好像差不多。

代码：

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 10005
#define M 400000
#define K 1200000
using namespace std;
vector<int>to[N];
int n,m,fa[N],H[N],S,T,ans;
int son[N],si[N],dis[M],Q[M];
int rt[M],tot,ls[M],rs[M],tim[M],Lim;
int TOT=1,LA[M],NE[K],EN[K],G[K];
void ADD(int x,int y,int z)
{
	TOT++;
	G[TOT]=z;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void Link(int x,int y,int z)
{
	if(!x||!y)return;
	ADD(x,y,z);
	ADD(y,x,0);
}
int CP(int p)
{
	int o=++tot;
	ls[o]=ls[p];
	rs[o]=rs[p];
	tim[o]=Lim;
	return o;
}
int Ins(int p,int l,int r,int x,int k)
{
	int o=tim[p]==Lim?p:CP(p);
	if(o!=p)Link(o,p,1e9);
	if(l==r)return Link(o,k,1e9),o;
	int ll,rr,mid=l+r>>1;
	if(x<=mid)
	{
		ll=ls[o];ls[o]=Ins(ls[o],l,mid,x,k);
		if(ll!=ls[o])Link(o,ls[o],1e9);
	}
	else
	{
		rr=rs[o];rs[o]=Ins(rs[o],mid+1,r,x,k);
		if(rr!=rs[o])Link(o,rs[o],1e9);
	}
	return o;
}
void Gedge(int p,int l,int r,int x,int y,int k)
{
	if(!p)return;
	if(x<=l&&y>=r){Link(k,p,1e9);return;}
	int mid=l+r>>1;
	if(x<=mid&&y>=l)Gedge(ls[p],l,mid,x,y,k);
	if(x<=r&&y>mid)Gedge(rs[p],mid+1,r,x,y,k);
}
void Merge(int x,int &p)
{
	p=Ins(p,1,n,H[x],x);
	for(int i=0;i<to[x].size();i++)Merge(to[x][i],p);
}
void DFS(int x)
{
	int i,y;si[x]=1;
	for(i=0;i<to[x].size();i++)
	{
		y=to[x][i];DFS(y);si[x]+=si[y];
		if(si[y]>si[son[x]])son[x]=y;
	}
	Lim=x;rt[x]=Ins(rt[son[x]],1,n,H[x],x);
	for(i=0;i<to[x].size();i++)
	{
		y=to[x][i];
		if(y!=son[x])Merge(y,rt[x]);
	}
}
bool bfs()
{
	int i,x,y,hd,tl;
	for(i=1;i<=T;i++)dis[i]=-1;
	hd=tl=1;Q[1]=S;dis[S]=0;
	while(hd<=tl)
	{
		x=Q[hd++];
		for(i=LA[x];i;i=NE[i])
		{
			y=EN[i];
			if(!G[i]||dis[y]!=-1)continue;
			dis[y]=dis[x]+1;
			Q[++tl]=y;
			if(y==T)return 1;
		}
	}
	return 0;
}
int dfs(int x,int f)
{
	if(x==T)return f;
	int i,y,tmp,d=0;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(!G[i]||dis[y]!=dis[x]+1)continue;
		tmp=dfs(y,min(f-d,G[i]));
		d+=tmp;G[i]-=tmp;G[i^1]+=tmp;
		if(d==f)break;
	}
	if(!d)dis[x]=-1;return d;
}
int main()
{
	int i,j,k,l,r,d,t;
	scanf("%d%d",&n,&m);tot=n+m;
	for(i=2;i<=n;i++)scanf("%d",&t),to[t].push_back(i);
	for(i=1;i<=n;i++)scanf("%d",&H[i]);
	DFS(1);S=tot+1;T=S+1;
	for(i=1;i<=n;i++)Link(i,T,1);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&l,&r,&d,&t);
		Link(S,n+i,t);Gedge(rt[d],1,n,l,r,n+i);
	}
	while(bfs())ans+=dfs(S,1e9);
	printf("%d",ans);
}