[UOJ UNR#1]奇怪的线段树

来自FallDream的博客，未经允许，请勿转载， 谢谢。

---

原题可以到UOJ看，传送门

如果存在一个点是白的，却有儿子是黑的，显然无解。

不然的话，只要所有黑色的“黑叶子”节点，即没有黑色的儿子的节点有访问到就行了。

联想到今年CTSC上一道题叫“被操纵的线段树”，每个点被访问之后，可以和他合并的点满足左端点是它的右端点+1，并且和它没有相同的父亲。

发现这些点构成一条链，所以只需要向最大的那个点连边就行了，然后每个点向左儿子连边。

拆点之后，给所有的“黑色叶子”节点中间的边加上流量下界，求出最小流就是答案了。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#define S 0

#define T 16001

#define SS 16002

#define TT 16003

#define MN 16003

#define INF 2000000000

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,q[MN+],c[MN+],d[MN+],head[MN+],cnt=,Lt[MN+],Rt[MN+],dn=,m;

int in[MN+],L[MN+],R[MN+],s[MN+],ss[MN+],fa[MN+],top;

struct edge{int to,next,w;}e[MN*+];

vector<int> v[MN+];

inline void ins(int f,int t,int w)

{

    e[++cnt]=(edge){t,head[f],w};head[f]=cnt;

    e[++cnt]=(edge){f,head[t],};head[t]=cnt;

}

int Build(int l,int r)

{

    int x=++dn;s[x]=read();Lt[x]=l;Rt[x]=r;v[l].push_back(x);

    if(l!=r)

    {

        int mid=read();

        fa[L[x]=Build(l,mid)]=x;

        fa[R[x]=Build(mid+,r)]=x;

        ss[x]|=ss[L[x]]|ss[R[x]];

        if(!s[x]&&ss[x]){puts("OwO");exit();}

        ins(x,L[x],INF);

    }

    if(ss[x]|s[x]) ins(x,x+m,INF);

    if(s[x]&&!ss[x]) ins(S,x,INF),--in[x],++in[x+m],ins(x+m,T,INF);

    ss[x]|=s[x];return x;

}

bool bfs()

{

    memset(d,,sizeof(d));int i,j;

    for(d[q[top=i=]=SS]=;i<=top;++i)

        for(j=c[q[i]]=head[q[i]];j;j=e[j].next)

            if(e[j].w&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+;

    return d[TT];

}

int dfs(int x,int f)

{

    if(x==TT) return f;int used=;

    for(int&i=c[x];i;i=e[i].next)

        if(e[i].w&&d[e[i].to]==d[x]+)

        {

            int w=dfs(e[i].to,min(f-used,e[i].w));

            used+=w;e[i].w-=w;e[i^].w+=w;

            if(used==f) return f;

        }

    return d[x]=-,used;

}

int main()

{

    n=read();m=*n-;Build(,n);

    for(int i=,j,k;i<=dn;++i)

        for(j=,k=Rt[i]+;j<v[k].size();++j)

            if(v[k][j]!=R[fa[i]]) {ins(i+m,v[k][j],INF);break;}

    for(int i=;i<=dn<<;++i) if(in[i]>) ins(SS,i,in[i]); else if(in[i]<) ins(i,TT,-in[i]);

    while(bfs()) dfs(SS,INF);ins(T,S,INF);

    while(bfs()) dfs(SS,INF);

    printf("%d\n",e[cnt].w);

    return ;

}