Description
给出一棵二叉树的结构，每次询问一个区间，将路径上的点染黑，求最小询问次数。
Solution
网络流。
好厉害的题啊 =w=。
首先可以发现的是，询问一个区间，一定是一段连续的左节点加上一段连续的右节点。
如果是左节点，代表区间([l,r])，那么另一个询问的端点一定是([r+1,x])的左节点，也就是说不能出现左右两个节点，因为这样可以向上合并。
如果是右节点，那么只需要满足另一个端点是(r+1)即可。
这样可以跑最小流，首先拆一下点，如果不是最下面的节点，那么对于它其实没有限制，因为如果满足了它下面的节点，它一定有流量。
如果是下面的节点，那么最小流量就是1
题解里好像建了辅助节点，来优化建图。
我并没有建辅助节点，而是将树上的左节点连接起来，因为满足条件的是一段左端点相同的点，所以直连左节点即可。
建树的同时，记录一下左端点为(x)的最靠上的点。
对于右节点就直接连最上面的点即可，左节点就连最上面的点的左节点即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define cg (2*n-1)
#define lc(o) ch[o][0]
#define rc(o) ch[o][1]
const int N = 4080*4;
const int oo = 0x3f3f3f3f;
inline int in(int x=0,char ch=getchar()) { while(ch>'9' || ch<'0') ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x; }
int n,rt,flag;
int ch[N][2],b[N],f[N],bb[N],L[N],R[N],tp[N];
struct Edge { int fr,to,fl; };
struct Network {
vector<Edge> edge;
vector<int> g[N];
int S,T,s,t,cnt,k,d[N],cur[N],du[N],p[N];
void AddEdge(int fr,int to,int fl) {
edge.push_back((Edge) { fr,to,fl });
edge.push_back((Edge) { to,fr, 0 });
g[fr].push_back(edge.size()-2);
g[to].push_back(edge.size()-1);
}
void AddEdge(int fr,int to,int l,int r) {
AddEdge(fr,to,r-l),du[fr]-=l,du[to]+=l;
}
int BFS(int s,int t) {
memset(d,0xff,sizeof(d));
queue<int> q;
d[s]=1,q.push(s);
for(int x;!q.empty();) {
x=q.front(),q.pop();
for(int i=0;i<(int)g[x].size();i++) {
Edge &e=edge[g[x][i]];
if(e.fl && d[e.to]==-1) d[e.to]=d[x]+1,q.push(e.to);
}
}return d[t]!=-1;
}
int Dinic(int s,int t) {
int flow=0;
for(int x;BFS(s,t);) {
// puts("qqqwq");
for(memset(cur,0,sizeof(cur)),x=s,k=0;;) {
if(x==t) {
int mine=0,minf=oo;
for(int i=0;i<k;i++)
if(edge[p[i]].fl<minf) minf=edge[p[i]].fl,mine=i;
for(int i=0;i<k;i++)
edge[p[i]].fl-=minf,edge[p[i]^1].fl+=minf;
flow+=minf,k=mine,x=edge[p[mine]].fr;
}
for(int &i=cur[x];i<(int)g[x].size();i++) {
Edge &e=edge[g[x][i]];
if(d[x]+1==d[e.to] && e.fl) break;
}
if(cur[x]<(int)g[x].size()) {
p[k++]=g[x][cur[x]],
x=edge[g[x][cur[x]]].to;
} else {
if(!k) break;
d[x]=-1,x=edge[p[--k]].fr;
}
}
// cout<<flow<<endl;
}return flow;
}
void Build(int &x,int l,int r) {
x=++cnt;
if(!tp[l]) tp[l]=x;
L[x]=l,R[x]=r;
if(l==r) {
bb[x]=b[x]=in();
if(b[x]) AddEdge(x,x+cg,1,oo);
} else {
b[x]=in();
int m=in();
Build(lc(x),l,m),Build(rc(x),m+1,r);
AddEdge(x+cg,lc(x),0,oo);
if(bb[lc(x)]||bb[rc(x)]) {
if(!b[x]) flag=1;
else AddEdge(x,x+cg,0,oo);
} else {
if(b[x]) AddEdge(x,x+cg,1,oo);
}
bb[x]=b[x]||bb[lc(x)]||bb[rc(x)];
f[lc(x)]=f[rc(x)]=x;
}
}
void main() {
flag=0;
n=in();
S=++cnt,T=++cnt,s=++cnt,t=++cnt;
Build(rt,1,n);
// puts("qwq");
if(flag) { cout<<"OwO"<<endl;return; }
for(int i=1;i<=cg;i++) {
AddEdge(s,cnt-cg+i,0,oo);
AddEdge(cnt+i,t,0,oo);
}
for(int i=cnt-cg+2;i<=cnt;i++) {
int d=rc(f[i])==i;
// cout<<d<<endl;
if(!d) {
if(tp[R[i]+1] && lc(tp[R[i]+1]))
AddEdge(i+cg,lc(tp[R[i]+1]),0,oo);
} else {
if(tp[R[i]+1])
AddEdge(i+cg,tp[R[i]+1],0,oo);
}
}
cnt+=cg;
for(int i=3;i<=cnt;i++) {
if(du[i]<0) AddEdge(i,T,-du[i]);
else if(du[i]>0) AddEdge(S,i,du[i]);
}
// for(int i=1;i<=cnt;i++) cout<<du[i]<<" ";cout<<endl;
// for(int i=0;i<(int)edge.size();i+=2) {
// cout<<edge[i].fr<<"-->"<<edge[i].to<<" "<<edge[i].fl<<endl;
// }
Dinic(S,T);
AddEdge(t,s,oo);
cout<<Dinic(S,T)<<endl;
}
}py;
int main() {
py.main();
return 0;
}