Original link: https://www.shuizilong.com/house/archives/bzoj-3681-arietta/
Network flow modeling is simpler than the above problem.
The functional segment tree aspect requires segment tree merging.
Still, it’s simpler than the previous question.
const int N = int(1e4) + 9; int T[N], H[N]; VI adj[N]; int n, m; namespace Chairman_Tree { #define lx c[0][x] #define rx c[1][x] #define ly c[0][y] #define ry c[1][y] #define ml ((l+r)>>1) #define mr (ml+1) #define lc lx, l, ml #define rc rx, mr, r const int NN = 100*N; int c[2][NN]; int s[NN]; int tot; int pp; int new_node() { return ++tot; } void upd(int x) { s[x] = s[lx] + s[rx]; } void Init(int &x, int l = 1, int r = n) { x = new_node(); if (l == r) { s[x] = 1; } else { if (pp < mr) Init(lc); else Init(rc); upd(x); } } int Merge(int x, int y, int l = 1, int r = n) { if (!x || !y) return x | y; if (l == r) { s[x] += s[y]; return x; } lx = Merge(lx, ly, l, ml); rx = Merge(rx, ry, mr, r); upd(x); return x; } void Query(int x, int l, int r, int a, int b, VI& L) { if (!x || b < l || r < a) return; if (a <= l && r <= b) { L.PB(x); } else { Query(lc, a, b, L); Query(rc, a, b, L); } } } using namespace Chairman_Tree; void dfs(int u = 1) { pp = H[u]; Init(T[u]); for (auto v: adj[u]) { dfs(v); T[u] = Merge(T[u], T[v]); } } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); #endif RD(n, m); FOR_1(i, 2, n) adj[RD()].PB(i); REP_1(i, n) RD(H[i]); dfs(); atcoder::mf_graph<int> G(n+m+2+tot); int s = n+m, t = n+m+1; FOR(x, 1, tot) { if (lx) G.add_edge(t+x, t+lx, INF); if (rx) G.add_edge(t+x, t+rx, INF); } REP_1(i, n) { VI L; Query(T[i], 1, n, H[i], H[i], L); G.add_edge(t+L[0], t, 1); } REP(i, m) { int l, r, d; RD(l, r, d); G.add_edge(s, i, RD()); VI L; Query(T[d], 1, n, l, r, L); for (auto l: L) G.add_edge(i, t+l, INF); } cout << G.flow(s, t) << endl; }
This article is reprinted from: https://www.shuizilong.com/house/archives/bzoj-3681-arietta/
This site is for inclusion only, and the copyright belongs to the original author.