一棵有根树, 每个点有权值Hi. m个操作, 每个可以选择子树Di中权值在[Li,Ri]中的任意不超过Ti个点. 问所有操作后最多能选择多少个点. (1≤n,m≤10^4, 1≤Hi,Ti≤n, 1≤Li≤Ri≤n) 一开始没什么头绪. 数据范围有点奇怪.
突然发现了一个匹配的模型......线段树优化网络流建图? 这里同样既有位置区间限制, 又有值域限制, 可持久化线段树? 但这不是前缀区间......树套树? 空间复杂度就爆了......线段树合并的过程能不能可持久化? 诶, 貌似可以......
瞥了一眼题解......还真是这样......我在想要不要同时合并几棵树而不仅限于两棵, 因为直接可持久化产生了不少无用点. 题解是两棵两棵合并的, 于是我也这样做了.
WA了一发, 因为我把题目看错了. 问的不是最多能选择多少个权值, 而是多少个点......
平常我们只说线段树合并是
别忘了构建每个叶子的花费. 可持久化线段树部分总共开
const int N = 10001, MAXV = 2+2*N+30*N, MAXE = 770000, inf = 1e8;
struct MaximumFlow
{
struct Edge
{
int to, c, nxt;
} E[2+MAXE*2];
int n, s, t, lv[MAXV], adj[MAXV], cur[MAXV], Q[MAXV];
void add(int u, int v, int f)
{
static int ptr = 2;
E[ptr] = (Edge){v, f, adj[u]};
adj[u] = ptr++;
E[ptr] = (Edge){u, 0, adj[v]};
adj[v] = ptr++;
}
bool bfs()
{
memset(lv, -1, sizeof(int)*n);
int* p = Q, * q = Q+1;
Q[0] = s;
lv[s] = 0;
while (p != q)
{
int u = *p++;
for (int i = adj[u]; i; i = E[i].nxt)
{
int v = E[i].to;
if (E[i].c && lv[v] == -1)
{
lv[v] = lv[u] + 1;
*q++ = v;
}
}
}
return lv[t] != -1;
}
int dfs(int u, int f)
{
if (u == t) return f;
int r = f;
for (int& i = cur[u]; i; i = E[i].nxt)
{
int v = E[i].to;
if (lv[v] == lv[u] + 1 && E[i].c)
{
int t = dfs(v, min(E[i].c, r));
E[i].c -= t;
E[i^1].c += t;
r -= t;
if (!r) break;
}
}
return f-r;
}
int solve(int _s, int _t, int _n)
{
s = _s, t = _t, n = _n;
int f = 0;
while (bfs())
{
rep (i, 0, n) cur[i] = adj[i];
f += dfs(s, inf);
}
return f;
}
} solver;
int n;
vector<int> adj[N];
struct Seg
{
int ptr, lc[N*30], rc[N*30];
void add(int u, int v)
{
solver.add(u+n, v+n, inf);
}
int merge(int x, int y, int l, int r)
{
if (!x || !y) return x+y;
int m = (l+r)/2, o = ++ptr;
if (l == r)
{
add(o, x);
add(o, y);
}
else
{
lc[o] = merge(lc[x], lc[y], l, m);
rc[o] = merge(rc[x], rc[y], m+1, r);
if (lc[o]) add(o, lc[o]);
if (rc[o]) add(o, rc[o]);
}
return o;
}
int build(int x, int i, int l, int r)
{
int o = ++ptr;
if (l == r)
{
solver.add(o+n, i, inf);
}
else
{
int m = (l+r)/2;
if (x <= m) add(o, lc[o] = build(x, i, l, m));
else add(o, rc[o] = build(x, i, m+1, r));
}
return o;
}
void query(int L, int R, int i, int o, int l, int r)
{
if (!o) return;
if (L <= l && r <= R)
return solver.add(i, o+n, inf), void();
int m = (l+r)/2;
if (L <= m) query(L, R, i, lc[o], l, m);
if (R > m) query(L, R, i, rc[o], m+1, r);
}
} T;
int h[N], rt[N];
void dfs(int u)
{
rt[u] = T.build(h[u], u, 1, n);
rep (i, 0, adj[u].size())
{
int v = adj[u][i];
dfs(v);
rt[u] = T.merge(rt[u], rt[v], 1, n);
}
}
int main()
{
int m;
scanf("%d%d", &n, &m);
rep (i, 2, n+1)
{
int p;
scanf("%d", &p);
adj[p].push_back(i);
}
rep (i, 1, n+1) scanf("%d", h+i);
dfs(1);
int p = n + T.ptr + 1;
rep (i, 0, m)
{
int l, r, d, t;
scanf("%d%d%d%d", &l, &r, &d, &t);
solver.add(0, p, t);
T.query(l, r, p, rt[d], 1, n);
++p;
}
rep (i, 1, n+1) solver.add(i, p, 1);
printf("%d\n", solver.solve(0, p, p+1));
return 0;
}