一棵有根树，每个点有一个音高，有 $m$ 中弹奏方法，每种方法可以弹奏 $d$ 子树中音高在 $[l,r]$ 间的音符，每种方法最多弹 $t$ 次
求最多能弹出多少个音符
$n \leq 10000$
sol：
网络流
暴力连边是
1. $S \rightarrow 每个点$
2. $每个方法 \rightarrow T$
3. $每个点 \rightarrow 每个能用到的方法$
第一种边限制是 $1$ ，第二种边限制是 $t$，第三种边没有限制
第一第二种不好优化，考虑优化第三种
第三种本质上是对树上 $dfn$ 是一段区间（子树），权值也是一段区间的点连边
考虑数据结构优化
可以使用可持久化线段树合并
一开始每个点向它所在的线段树上的点连边
每次合并的时候原来的点向合并出来的新点连边
对于方法我们把它能作用的区域向它连边
这样边数是 $O(2n) + O(可持久化线段树)$ 的，大概是 $O(nlogn)$
#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {
int x = , f = ; char ch;
for (ch = getchar(); !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
for (; isdigit(ch); ch = getchar()) x = * x + ch - '';
return x * f;
}
const int maxn = , maxm = , inf = ;
struct Dinic {
int cur[maxm], head[maxm], nx[maxm];
int n, m, s, t;
struct Edge {
int from, to, caps;
Edge(){}
Edge(int _1, int _2, int _3): from(_1), to(_2), caps(_3) {}
}es[maxm];
void AddEdge(int u, int v, int w) {
es[m] = Edge(u, v, w); nx[m] = head[u]; head[u] = m++;
es[m] = Edge(v, u, ); nx[m] = head[v]; head[v] = m++;
}
void setn(int _) {n = _;}
Dinic() {m = ; memset(head, -, sizeof(head));}
queue<int> q; int dis[maxn];
bool BFS() {
rep(i, , n) dis[i] = ;
q.push(t); dis[t] = ;
while(!q.empty()) {
int now = q.front(); q.pop();
for(int i=head[now];~i;i=nx[i]) {
Edge &e = es[i^];
if(!dis[e.from] && e.caps) {
dis[e.from] = dis[now] + ;
q.push(e.from);
}
}
}
return (dis[s] > );
}
int DFS(int u, int a) {
if(u == t || !a) return a;
int flow = , f;
for(int &i = cur[u]; ~i; i = nx[i]) {
Edge &e = es[i];
if(dis[e.to] == dis[u] - && (f = DFS(e.to, min(e.caps, a)))) {
e.caps -= f; es[i^].caps += f;
a -= f; flow += f;
if(!a) return flow;
}
}
return flow;
}
int MaxFlow(int _s, int _t) {
s = _s, t = _t; int res = ;
while(BFS()) {
memcpy(cur, head, (n + ) * sizeof(int));
res += DFS(s, );
}
return res;
}
} sol;
int s, t, nodes;
struct Ques {
int l, r, d, t;
Ques(){}
Ques(int _1, int _2, int _3, int _4) : l(_1), r(_2), d(_3), t(_4) {}
}qs[maxn];
int n, m;
int fa[maxn], h[maxn];
int first[maxn], nx[maxn], to[maxn], cnt;
inline void add(int u, int v) {
to[++cnt] = v;
nx[cnt] = first[u];
first[u] = cnt;
}
int root[maxn], ls[maxm << ], rs[maxm << ], dfn;
inline void Insert(int &x, int l, int r, int pos, int p) {
x = ++dfn;
if(l == r) {
sol.AddEdge(p, x + nodes, inf);
return;
}
int mid = (l + r) >> ;
if(pos <= mid) Insert(ls[x], l, mid, pos, p) ;
else Insert(rs[x], mid + , r, pos, p) ;
if(ls[x]) sol.AddEdge(ls[x] + nodes, x + nodes, inf);
if(rs[x]) sol.AddEdge(rs[x] + nodes, x + nodes, inf);
}
inline int merge(int x, int y, int l, int r) {
if(!x || !y) return x + y;
int z = ++dfn;
if(l == r) {
sol.AddEdge(x + nodes, z + nodes, inf);
sol.AddEdge(y + nodes, z + nodes, inf);
return z;
}
int mid = (l + r) >> ;
ls[z] = merge(ls[x], ls[y], l, mid);
rs[z] = merge(rs[x], rs[y], mid+, r);
if(ls[z]) sol.AddEdge(ls[z] + nodes, z + nodes, inf);
if(rs[z]) sol.AddEdge(rs[z] + nodes, z + nodes, inf);
return z;
}
inline void link(int x, int l, int r, int L, int R, int p) {
if(!x) return;
if(L <= l && r <= R) {
sol.AddEdge(x + nodes, p, inf);
return;
}
int mid = (l + r) >> ;
if(L <= mid) link(ls[x], l, mid, L, R, p);
if(R > mid) link(rs[x], mid+, r, L, R, p);
}
inline void dfs(int x) {
Insert(root[x], , n, h[x], x);
for(int i=first[x];i;i=nx[i]) {
dfs(to[i]);
root[x] = merge(root[x], root[to[i]], , n);
}
} int main() {
n = read(), m = read();
s = n + m + , t = n + m + , nodes = t + ;
rep(i, , n) {
fa[i] = read();
add(fa[i], i);
}
rep(i, , n) {
h[i] = read();
sol.AddEdge(s, i, );
} dfs();
rep(i, , m) {
int l = read(), r = read(), d = read(), ct = read();
link(root[d], , n, l, r, i+n);
qs[i] = Ques(l, r, d, ct); sol.AddEdge(i + n, t, ct);
}
sol.setn(nodes + dfn + );
cout << sol.MaxFlow(s, t) << endl;
}