Description：

给出一棵不一定平均划分的线段树，有一些点是黑色的，问最少几次区间操作把经过的路径标黑可以得到。

$1\leqslant n\leqslant 4000$

Solution：

首先判无解，如果有一个节点不是黑色但是儿子有黑色就无解，否则一定有解。

然后我们发现如果只保留子树内没有黑色点的点，然后依次区间操作只会把最后定位到的区间染黑，这个问题和原问题是等价的，那么我们观察一次区间操作最后会定位到的节点，应该是连续的一段右儿子和连续的一段左儿子，然后有一个定理就是对于所有的连续的一段右儿子加连续的一段左儿子都可以通过一次区间定位得到，那么我们可以把每个右儿子往后面的连续的任意区间连边，左儿子往后面连续的左儿子连边，要求把所有的有标记的都有流过，没有标记的没有流过，这就是一个有上下界的最小流问题了，但是这样可能会连 $O(n^2)$ 条边，我们考虑优化，发现实际上左儿子往后连的边不是复杂度瓶颈，但是右儿子会往右边连很多边，对于每两个位置之间新建一个点，然后每个右儿子右端点往这个点连，这个点往所有区间左端点连即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

#pragma GCC optimaze(2)

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 4010

#define R register

#define I inline

int cnt = 0;

vector<int> ls[MAXN],rs[MAXN];

struct node

{

	int a,b,l,r,lc,rc,mid,col,tag,exi,tp;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

int flag;

I void build(int &rt,int l,int r,int tp)

{

	rt = newnode();

	t[rt].a = ++cnt;t[rt].b = ++cnt;

	t[rt].tp = tp;

	t[rt].l = l;t[rt].r = r;

	if(tp == 0)ls[l].push_back(rt);

	if(tp == 1)rs[l].push_back(rt);

	t[rt].col = t[rt].tag = rd();//cout << rt << " " << t[rt].l << " " << t[rt].r << " : " << t[rt].a << " " << t[rt].b << endl;

	if(l == r)return;

	t[rt].mid = rd();

	build(t[rt].lc,l,t[rt].mid,0);

	build(t[rt].rc,t[rt].mid + 1,r,1);

	t[rt].exi = t[rt].tag | t[t[rt].lc].exi | t[t[rt].rc].exi;

	if(t[rt].exi && !t[rt].tag)flag = true;

	return;

}

I void gettag(int rt,int l,int r)

{

	if(l == r){/*cout << l << " " << r << " " << t[rt].tag << endl;*/return;}

	t[rt].tag = t[rt].tag & (!t[t[rt].lc].tag) & (!t[t[rt].rc].tag);//cout << l << " " << r << " " << t[rt].tag << endl;

	gettag(t[rt].lc,l,t[rt].mid);gettag(t[rt].rc,t[rt].mid + 1,r);

	return;

}

int id[MAXN];

#define iter vector<int>::iterator

#define MAXP (MAXN * 4)

int S,T,ss,tt;

struct edge

{

    int to,nxt,f;

}e[220000];

int edgenum = 0;

int lin[MAXP];

I void add(int a,int b,int f)

{//cout << a << " - > " << b << " : " << f << endl;

	e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

	return;

}

int ind[MAXP];

I void adde(int a,int b,int l,int h)

{//cout << a << " " << b << " " << l << " " << h << endl;

	add(a,b,h - l);

	ind[a] -= l;ind[b] += l;

	return;

}

int ch[MAXP];

int head[MAXP];

I bool BFS()

{

	R queue<int> q;q.push(ss);

	memset(ch,-1,sizeof(ch));ch[ss] = 0;

	while(!q.empty())

	{

		R int k = q.front();q.pop();

		for(R int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}//cout << "st BFS" << endl;

	return (ch[tt] != -1);

}

I int flow(int k,int f)

{

	if(k == tt)return f;

	R int r = 0;

	for(R int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			R int l = flow(e[i].to,min(f - r,e[i].f));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

		lin[k] = i;

	}

	if(r == 0)ch[k] = -1;

	return r;

}

#define INF 0x3f3f3f3f

I int dinic()

{

	R int ans = 0,r;

	memcpy(head,lin,sizeof(lin));

	while(BFS())

	{

		R int r = flow(ss,INF);//cout << r << endl;

		ans += r;

		memcpy(lin,head,sizeof(lin));

	}

	return ans;

}

int minflow()

{

	ss = T + 1;tt = ss + 1;

	for(R int i = 1;i <= T;++i)

	{

		if(ind[i] > 0)add(ss,i,ind[i]);

		if(ind[i] < 0)add(i,tt,-ind[i]);

	}

	dinic();

	add(T,S,INF);

	return dinic();

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	build(root,1,n,0);

	if(flag)

	{

		puts("OwO");

		return 0;

	}

	gettag(root,1,n);

	for(R int i = 1;i < n;++i)id[i] = ++cnt;

	S = cnt + 1;T = S + 1;

	for(R int i = 1;i <= ptr;++i)

	{

		//cout << " : " << i << " " << t[i].tp << endl;

		adde(S,t[i].a,0,INF);adde(t[i].b,T,0,INF);if(t[i].col)adde(t[i].a,t[i].b,t[i].tag,INF);

		if(t[i].tp == 0)

		{

			R int p = t[i].r + 1;

			for(R iter it = ls[p].begin();it != ls[p].end();++it)adde(t[i].b,t[*it].a,0,INF);

			if(t[i].l != 1)adde(id[t[i].l - 1],t[i].a,0,INF);

		}

		else

		{

			R int p = t[i].r + 1;

			for(R iter it = rs[p].begin();it != rs[p].end();++it)adde(t[i].b,t[*it].a,0,INF);

			if(t[i].r != n)adde(t[i].b,id[t[i].r],0,INF);

		}

	}

	cout << minflow() << endl;

	return 0;

}