【BZOJ 3681】Arietta

トランスファゲート
タイトルの説明
Ariettaの運命は妹とは違って、妹が学院に入ったとき、彼女はまだ山村に残っていた.しかし、彼女は恋人のVeldingとの手紙のやりとりを止めたことがない.ある日、彼女は彼を訪ねるつもりだ.窓の外の日差しに向かって、出発する前に彼女は再び琴を弾いた.彼女の琴の発声は非常に特殊だ.形式化された定義をあげましょう.すべてのn個の音符は音符C(1番ノード)からなる根木を形成し,各音符に音高Hiがある.Ariettaにはm個の力があり,i番目の力でDiノードのサブツリーから[Li,Ri]のいずれかの音符を弾き出すことができる.楽曲の調和のため、アリエッタは最大でi番目の力Ti回を弾く.Ariettaは彼女がどれだけの音符を弾けるか知りたい.
Sol
明らかに最大の重みマッチング問題であり、ネットワークストリームで解決されます.
暴力のエッジ数は明らかに爆発しているので、データ構造でエッジを最適化すればいいです.
ここはサブツリーである以上、自然に線分ツリーを組み合わせてメンテナンスすればよい.
マージのたびに新しいポイントを作成し、エッジを接続します.そして葉ノードは,複数の点に同じHがある可能性があることに注意するので,新しい点を元の点にそれぞれ1つの辺を結ぶべきである.
code:

#include
using namespace std;
#define Set(a,b) memset(a,b,sizeof(a))
template<class T>inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}typedef long long ll;
const int N=1e4+10;
const int MAXN=4e5;
const int MAXM=1e6;
const int INF=1e9;
int H[N],rt[N],ls[MAXN],rs[MAXN];int n,m;
vector<int> Son[N];
int cur=0,S,T;
struct edge{
	int to,next,cap;
}a[MAXM<<1];
int head[MAXN],cnt=0,d[MAXN];
inline void add(int x,int y,int z){a[cnt]=(edge){y,head[x],z};head[x]=cnt++;}
inline void add_edge(int x,int y,int z){add(x,y,z),add(y,x,0);}
inline void Insert(int&u,int l,int r,int i){
	u=++cur;if(l==r) return add_edge(T+u,i,INF);
	int mid=(l+r)>>1;
	if(mid>=H[i]) Insert(ls[u],l,mid,i),add_edge(T+u,T+ls[u],INF);
	else          Insert(rs[u],mid+1,r,i),add_edge(T+u,T+rs[u],INF);
	return;
}
void Link(int u,int l,int r,int L,int R,int p){
	if(!u) return;
	if(l>=L&&r<=R) return add_edge(p,T+u,INF);
	int mid=(l+r)>>1;
	if(mid>=L) Link(ls[u],l,mid,L,R,p);
	if(mid< R) Link(rs[u],mid+1,r,L,R,p);
	return;
}
int Merge(int u,int v,int l,int r) {
	if(!u||!v) return u|v;int p=++cur;
	if(l==r) {
		add_edge(T+p,T+u,INF),add_edge(T+p,T+v,INF);
		return p;
	}int mid=(l+r)>>1;
	ls[p]=Merge(ls[u],ls[v],l,mid);
	rs[p]=Merge(rs[u],rs[v],mid+1,r);
	if(ls[p]) add_edge(T+p,T+ls[p],INF);
	if(rs[p]) add_edge(T+p,T+rs[p],INF);
	return p;
}
void dfs(int u){
	Insert(rt[u],1,n,u);
	vector<int>::iterator iter;
	for(iter=Son[u].begin();iter!=Son[u].end();++iter) {int v=*iter;dfs(v);rt[u]=Merge(rt[u],rt[v],1,n);}
	return;
}
int TAIL,now[MAXN];
int dfs(int u,int flow){
	if(u==T) return flow;
	int res=flow;
	for(int v,&i=now[u];~i;i=a[i].next) {
		v=a[i].to;if(!a[i].cap||d[v]!=d[u]+1) continue;
		int f=dfs(v,min(res,a[i].cap));
		a[i].cap-=f,a[i^1].cap+=f,res-=f;
		if(!f) d[v]=0;
		if(!res) break;
	}return flow-res;
}
queue<int> Q;
inline bool bfs(){
	while(!Q.empty()) Q.pop();
	for(int i=0;i<=TAIL;++i) d[i]=0;
	d[S]=1;Q.push(S);
	while(!Q.empty()) {
		int u=Q.front();Q.pop();
		for(int v,i=head[u];~i;i=a[i].next) {
			v=a[i].to;if(!a[i].cap||d[v]) continue;
			d[v]=d[u]+1;if(v==T) return 1;
			Q.push(v);
		}
	}
	return d[T];
}
inline int Dinic(){int flow=0;while(bfs()) {for(int i=S;i<=TAIL;++i) now[i]=head[i];flow+=dfs(S,INF);}return flow;}
int main()
{
	freopen("data.in","r",stdin);
	freopen("my.out","w",stdout);
	init(n),init(m);int f;Set(head,-1);
	for(int i=2;i<=n;++i) init(f),Son[f].push_back(i);
	S=0,T=n+m+1;
	for(int i=1;i<=n;++i) init(H[i]),add_edge(i,T,1);
	dfs(1);
	for(int i=1;i<=m;++i) {
		int L,R,D,Ti;
		init(L),init(R),init(D),init(Ti);
		add_edge(S,i+n,Ti);Link(rt[D],1,n,L,R,i+n);
	}TAIL=T+cur;printf("%d
",Dinic());
	return 0;
}