[dsu on Tree + 主席树 优化建图] BZOJ3681 Arietta

比较经典的优化建图。网络流模型很显然,注意考虑如何优化建图。

注意有个子树的限制,而优化建图肯定不能信息相减得到子树对应的线段树。、

所以有个比较好的方法是 \(Dsu\ on\ tree\) 的思路建主席树。这样能得到每个子树对应的主席树了。

然后就是注意细节... 卡卡内存......

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
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int N,S,T;
namespace D{
const int maxn=1300005,maxe=2500005;
struct Edge{
int to,flow;
Edge(int t2=0,int t3=0){ to=t2; flow=t3; }
} Es[maxe];
int d[maxn],nxt[maxe],nfir[maxn],fir[maxn],tot=1;
queue<int> que;
void add(int x,int y,int w){
Es[++tot]=Edge(y,w);
nxt[tot]=fir[x]; fir[x]=tot;
Es[++tot]=Edge(x,0);
nxt[tot]=fir[y]; fir[y]=tot;
}
bool BFS(){
memset(d,63,sizeof(d)); int INF=d[0];
while(!que.empty()) que.pop();
que.push(S); d[S]=0;
while(!que.empty()){
int x=que.front(); que.pop();
for(int j=fir[x];j;j=nxt[j]) if(d[Es[j].to]==INF&&Es[j].flow>0){
d[Es[j].to]=d[x]+1; que.push(Es[j].to);
}
}
return d[T]!=INF;
}
int find_DFS(int x,int flw){
if(x==T||flw==0) return flw;
int res=0,t;
for(int &j=nfir[x];j;j=nxt[j]){
if(d[x]+1==d[Es[j].to]&&(t=find_DFS(Es[j].to,min(flw,Es[j].flow)))>0){
Es[j].flow-=t; Es[j^1].flow+=t;
res+=t; flw-=t; if(flw==0) break;
}
}
return res;
}
int Dinic() {
int MaxFlow=0,now;
while(BFS()){
for(int i=1;i<=N;i++) nfir[i]=fir[i];
MaxFlow+=find_DFS(S,1e+9);
}
return MaxFlow;
}
};
const int maxn=10005,maxe=20005;
int N_seg,ch[1300005][2],rt[1300005];
int Update(int pre,int L,int R,int pos,int id){
int p=++N_seg; if(pre) D::add(p,pre,1e9);
ch[p][0]=ch[pre][0]; ch[p][1]=ch[pre][1];
if(L==R) return D::add(p,id,1e9), p;
int mid=(L+R)>>1;
if(pos<=mid) ch[p][0]=Update(ch[pre][0],L,mid,pos,id);
else ch[p][1]=Update(ch[pre][1],mid+1,R,pos,id);
return p;
}
void Link(int p,int L,int R,int qL,int qR,int id){
if(!p||qR<L||R<qL) return;
if(qL<=L&&R<=qR) return D::add(id,p,1e9);
int mid=(L+R)>>1;
Link(ch[p][0],L,mid,qL,qR,id); Link(ch[p][1],mid+1,R,qL,qR,id);
}
int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int n,Q,h[maxn],sz[maxn],hvy[maxn],q[maxn];
void Travel(int x){
q[++q[0]]=x;
for(int j=fir[x];j;j=nxt[j]) Travel(son[j]);
}
void dfs(int x){
sz[x]=1;
for(int j=fir[x];j;j=nxt[j]){
dfs(son[j]); sz[x]+=sz[son[j]];
if(sz[hvy[x]]<sz[son[j]]) hvy[x]=son[j];
}
if(hvy[x]) rt[x]=rt[hvy[x]]; else rt[x]=0;
rt[x]=Update(rt[x],1,n,h[x],x);
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=hvy[x]){
q[0]=0; Travel(son[j]);
for(int i=1;i<=q[0];i++) rt[x]=Update(rt[x],1,n,h[q[i]],q[i]);
}
}
int main(){
freopen("bzoj3681.in","r",stdin);
freopen("bzoj3681.out","w",stdout);
scanf("%d%d",&n,&Q);
for(int i=2;i<=n;i++){
int x; scanf("%d",&x);
add(x,i);
}
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
N_seg=n; dfs(1);
for(int i=n+1;i<=N_seg;i++){
if(ch[i][0]) D::add(i,ch[i][0],1e9);
if(ch[i][1]) D::add(i,ch[i][1],1e9);
}
N=N_seg+Q; S=++N; T=++N;
for(int i=1;i<=n;i++) D::add(i,T,1);
for(int i=1;i<=Q;i++){
int L,R,x,y; scanf("%d%d%d%d",&L,&R,&x,&y);
D::add(S,N_seg+i,y);
Link(rt[x],1,n,L,R,N_seg+i);
}
printf("%d\n",D::Dinic());
return 0;
}