一棵有根树，每个点有一个音高，有 $m$ 中弹奏方法，每种方法可以弹奏 $d$ 子树中音高在 $[l,r]$ 间的音符，每种方法最多弹 $t$ 次
求最多能弹出多少个音符
$n leq 10000$
sol：
网络流
暴力连边是
1. $S ightarrow 每个点$
2. $每个方法 ightarrow T$
3. $每个点 ightarrow 每个能用到的方法$
第一种边限制是 $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 = 0, f = 1; char ch; for (ch = getchar(); !isdigit(ch); ch = getchar()) if (ch == '-') f = -f; for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0'; return x * f; } const int maxn = 100010, maxm = 1000010, inf = 2147483233; 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, 0); nx[m] = head[v]; head[v] = m++; } void setn(int _) {n = _;} Dinic() {m = 0; memset(head, -1, sizeof(head));} queue<int> q; int dis[maxn]; bool BFS() { rep(i, 0, n) dis[i] = 0; q.push(t); dis[t] = 1; while(!q.empty()) { int now = q.front(); q.pop(); for(int i=head[now];~i;i=nx[i]) { Edge &e = es[i^1]; if(!dis[e.from] && e.caps) { dis[e.from] = dis[now] + 1; q.push(e.from); } } } return (dis[s] > 1); } int DFS(int u, int a) { if(u == t || !a) return a; int flow = 0, f; for(int &i = cur[u]; ~i; i = nx[i]) { Edge &e = es[i]; if(dis[e.to] == dis[u] - 1 && (f = DFS(e.to, min(e.caps, a)))) { e.caps -= f; es[i^1].caps += f; a -= f; flow += f; if(!a) return flow; } } return flow; } int MaxFlow(int _s, int _t) { s = _s, t = _t; int res = 0; while(BFS()) { memcpy(cur, head, (n + 1) * sizeof(int)); res += DFS(s, 2147483233); } 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 << 1], rs[maxm << 1], 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) >> 1; if(pos <= mid) Insert(ls[x], l, mid, pos, p) ; else Insert(rs[x], mid + 1, 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) >> 1; ls[z] = merge(ls[x], ls[y], l, mid); rs[z] = merge(rs[x], rs[y], mid+1, 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) >> 1; if(L <= mid) link(ls[x], l, mid, L, R, p); if(R > mid) link(rs[x], mid+1, r, L, R, p); } inline void dfs(int x) { Insert(root[x], 1, n, h[x], x); for(int i=first[x];i;i=nx[i]) { dfs(to[i]); root[x] = merge(root[x], root[to[i]], 1, n); } } int main() { n = read(), m = read(); s = n + m + 1, t = n + m + 2, nodes = t + 1; rep(i, 2, n) { fa[i] = read(); add(fa[i], i); } rep(i, 1, n) { h[i] = read(); sol.AddEdge(s, i, 1); } dfs(1); rep(i, 1, m) { int l = read(), r = read(), d = read(), ct = read(); link(root[d], 1, n, l, r, i+n); qs[i] = Ques(l, r, d, ct); sol.AddEdge(i + n, t, ct); } sol.setn(nodes + dfn + 5); cout << sol.MaxFlow(s, t) << endl; }