P4787 [BalkanOI2018]Minmaxtree 题解

绝顶我为峰 · 2022-09-01 14:10:24 · 题解

逸延丁真，鉴定为大胖题。

很自然想到树剖一下维护第 i 条边的取值范围 [l_i,r_i]，具体来说是对所有最小值的限制取 \max，最大值的限制取 \min。

我们有结论：存在一种合法的构造，使得第 i 条边的边权不是 l_i 就是 r_i。

简单证明一下，首先边权不能取 (-\infty,l_i)\cup(r_i,\infty) 的部分，因为这样直接让一些限制不合法了，如果取值在 (l_i,r_i) 中间，那么这条边不会取到任意一条边的限制，挪动到一个端点是不劣的。

于是问题抽象成有 n 个布尔变量，有 m 条限制要求一个点集里面要存在 0/1，构造方案。

这是一个二分图最大匹配问题，左边 m 个点代表限制，右边 n 个点表示变量，右边每个点分别向上下界对应的限制连边，由于题目保证了所有限制的权值互不相同，所以边的数量是线性的。这样跑最大匹配，如果满流说明有解（事实上这题保证一定有解），然后根据残量网络直接构造方案即可。

思路很自然，然而有树剖和网络流二合一，代码很长。

时间复杂度 O(N\sqrt N+K\log^2N+N\log N)。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x;
}
struct flow
{
    struct edge
    {
        int nxt,to,weight;
    }e[1000001<<3];
    int tot=1,s,t,h[200001],dep[200001],cur[200001],ans;
    bool vis[200001];
    inline void add(int x,int y,int w)
    {
        e[++tot]={h[x],y,w};
        h[x]=tot;
    }
    inline bool bfs()
    {
        queue<int> q;
        for(int i=0;i<=t;++i)
        {
            vis[i]=0;
            dep[i]=0x3f3f3f3f;
            cur[i]=h[i];
        }
        dep[s]=0;
        q.emplace(s);
        while(!q.empty())
        {
            int k=q.front();
            q.pop();
            vis[k]=0;
            for(int i=h[k];i;i=e[i].nxt)
                if(e[i].weight&&dep[e[i].to]>dep[k]+1)
                {
                    dep[e[i].to]=dep[k]+1;
                    if(!vis[e[i].to])
                    {
                        vis[e[i].to]=1;
                        q.emplace(e[i].to);
                    }
                }
        }
        return dep[t]^dep[0];
    }
    inline int dfs(int k,int f)
    {
        if(k==t)
        {
            ans+=f;
            return f;
        }
        int r=0,used=0;
        for(int i=cur[k];i;i=e[i].nxt)
        {
            cur[k]=i;
            if(e[i].weight&&dep[e[i].to]==dep[k]+1)
                if((r=dfs(e[i].to,min(e[i].weight,f-used))))
                {
                    e[i].weight-=r;
                    e[i^1].weight+=r;
                    used+=r;
                    if(f==used)
                        break;
                }
        }
        return used;
    }
    inline void dinic()
    {
        while(bfs())
            dfs(s,1<<30);
    }
}flow;
int n,m,w[70001],ans[70001],dep[70001],fa[70001],s[70001],son[70001],top[70001],cnt,dfn[70001],val[70001<<2][2],tag[70001<<2][2];
map<int,int> mp;
vector<int> v[70001];
inline int ls(int k)
{
    return k<<1;
}
inline int rs(int k)
{
    return k<<1|1;
}
inline void push_up(int k)
{
    val[k][0]=max(val[ls(k)][0],val[rs(k)][0]);
    val[k][1]=min(val[ls(k)][1],val[rs(k)][1]);
}
inline void push_down(int k)
{
    if(tag[k][0]>=0)
    {
        val[ls(k)][0]=max(val[ls(k)][0],tag[k][0]);
        val[rs(k)][0]=max(val[rs(k)][0],tag[k][0]);
        tag[ls(k)][0]=max(tag[ls(k)][0],tag[k][0]);
        tag[rs(k)][0]=max(tag[rs(k)][0],tag[k][0]);
        tag[k][0]=-1;
    }
    if(tag[k][1]<=1e9)
    {
        val[ls(k)][1]=min(val[ls(k)][1],tag[k][1]);
        val[rs(k)][1]=min(val[rs(k)][1],tag[k][1]);
        tag[ls(k)][1]=min(tag[ls(k)][1],tag[k][1]);
        tag[rs(k)][1]=min(tag[rs(k)][1],tag[k][1]);
        tag[k][1]=1e9+7;
    }
}
inline void build(int k,int l,int r)
{
    tag[k][0]=-1;
    tag[k][1]=1e9+7;
    if(l==r)
    {
        val[k][0]=-1;
        val[k][1]=1e9+7;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    push_up(k);
}
inline void update1(int nl,int nr,int l,int r,int k,int p)
{
    if(nl>nr)
        return;
    if(l>=nl&&r<=nr)
    {
        val[k][0]=max(val[k][0],p);
        tag[k][0]=max(tag[k][0],p);
        return;
    }
    push_down(k);
    int mid=(l+r)>>1;
    if(nl<=mid)
        update1(nl,nr,l,mid,ls(k),p);
    if(nr>mid)
        update1(nl,nr,mid+1,r,rs(k),p);
    push_up(k);
}
inline void update2(int nl,int nr,int l,int r,int k,int p)
{
    if(nl>nr)
        return;
    if(l>=nl&&r<=nr)
    {
        val[k][1]=min(val[k][1],p);
        tag[k][1]=min(tag[k][1],p);
        return;
    }
    push_down(k);
    int mid=(l+r)>>1;
    if(nl<=mid)
        update2(nl,nr,l,mid,ls(k),p);
    if(nr>mid)
        update2(nl,nr,mid+1,r,rs(k),p);
    push_up(k);
}
inline pair<int,int> query(int node,int l,int r,int k)
{
    if(l==r)
        return {val[k][0],val[k][1]};
    push_down(k);
    int mid=(l+r)>>1;
    if(node<=mid)
        return query(node,l,mid,ls(k));
    return query(node,mid+1,r,rs(k));
}
inline void up1(int x,int y,int p)
{
    while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        update1(dfn[top[x]],dfn[x],1,n,1,p);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    update1(dfn[x]+1,dfn[y],1,n,1,p);
}
inline void up2(int x,int y,int p)
{
    while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        update2(dfn[top[x]],dfn[x],1,n,1,p);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    update2(dfn[x]+1,dfn[y],1,n,1,p);
}
inline void dfs1(int k,int f,int deep)
{
    dep[k]=deep;
    fa[k]=f;
    s[k]=1;
    for(int i:v[k])
    {
        if(i==f)
            continue;
        dfs1(i,k,deep+1);
        s[k]+=s[i];
        if(s[i]>s[son[k]])
            son[k]=i;
    }
}
inline void dfs2(int k,int t)
{
    top[k]=t;
    dfn[k]=++cnt;
    if(!son[k])
        return;
    dfs2(son[k],t);
    for(int i:v[k])
    {
        if(i==fa[k]||i==son[k])
            continue;
        dfs2(i,i);
    }
}
int main()
{
    freopen("minmaxtree.in","r",stdin);
    freopen("minmaxtree.out","w",stdout);
    n=read();
    for(int i=1;i<n;++i)
    {
        int x=read(),y=read();
        v[x].emplace_back(y);
        v[y].emplace_back(x);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n);
    m=read();
    flow.s=n+m+1;
    flow.t=flow.s+1;
    for(int i=1;i<=m;++i)
    {
        flow.add(flow.s,i,1);
        flow.add(i,flow.s,0);
        char opt=getchar();
        while(opt!='M'&&opt!='m')
            opt=getchar();
        int x=read(),y=read();
        w[i]=read();
        if(opt=='m')
            up1(x,y,w[i]);
        if(opt=='M')
            up2(x,y,w[i]);
        mp[w[i]]=i;
    }
    for(int i=2;i<=n;++i)
    {
        ans[i]=-1;
        flow.add(i+m,flow.t,1);
        flow.add(flow.t,i+m,0);
        pair<int,int> w=query(dfn[i],1,n,1);
        if(w.first>=0)
        {
            flow.add(mp[w.first],i+m,1);
            flow.add(i+m,mp[w.first],0);
        }
        if(w.second<=1e9)
        {
            flow.add(mp[w.second],i+m,1);
            flow.add(i+m,mp[w.second],0);
        }
    }
    flow.dinic();
    //cout<<flow.ans<<'\n';
    for(int k=1;k<=m;++k)
        for(int i=flow.h[k];i;i=flow.e[i].nxt)
            if(!flow.e[i].weight&&flow.e[i].to>m&&flow.e[i].to<=n+m)
            {
                ans[flow.e[i].to-m]=w[k];
                break;
            }
    for(int i=2;i<=n;++i)
    {
        if(ans[i]!=-1)
        {
            cout<<fa[i]<<" "<<i<<" "<<ans[i]<<'\n';
            continue;
        }
        pair<int,int> tmp=query(dfn[i],1,n,1);
        if(tmp.first==-1)
            tmp.first=0;
        cout<<fa[i]<<" "<<i<<" "<<tmp.first<<'\n';
    }
    return 0;
}