题目描述
Arietta 的命运与她的妹妹不同,在她的妹妹已经走进学院的时候,她仍然留在山村中。
但是她从未停止过和恋人 Velding 的书信往来。一天,她准备去探访他。 对着窗外的阳光,临行前她再次弹起了琴。 她的琴的发声十分特殊。 让我们给一个形式化的定义吧。 所有的 n 个音符形成一棵由音符 C ( 1 号节点) 构成的有根树,每一个音符有一个音高 Hi 。 Arietta 有 m 个力度,第 i 个力度能弹出 Di 节点的子树中,音高在 [Li,Ri] 中的任意一个音符。 为了乐曲的和谐,Arietta 最多会弹奏第 i 个力度 Ti 次。 Arietta 想知道她最多能弹出多少个音符。Sol
显然就是个最大权匹配问题，用网络流解决。
暴力连边边数显然爆炸，所以用个数据结构优化一下连边就可以了。
这里既然是子树那么自然就用线段树合并来维护就可以了。
每次合并的时候新建点并连边。然后叶子节点注意可能有多个点有相同的 H 所以应该新建点向原来的点各连一条边。
code:
#includeusing namespace std;#define Set(a,b) memset(a,b,sizeof(a))template 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 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 ::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 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\n",Dinic()); return 0;}