题解：P10787 [NOI2024] 树的定向

我感觉这题好爆了，思路非常的顺。

在特殊性质 A 下，将树黑白染色，可以构造出两种方案。将第一条边的方向钦定为

0

即可。

一般的情况中，将一条边定向后，可以将经过这条边且与这条边方向相反的限制全部忽略，然后这条边就可以缩起来。

当一条未被忽略的限制中只有一条边仍未被定向，那么这条边的方向就已经固定了。

当每条未被忽略的限制中均有至少两条边未被定向，就与特殊性质 A 等价了，此时给任意一条边任意定向都会有合法解。

于是算法流程就是：

尝试找到一条限制中只有一条边仍未被定向，若此限制不可被忽略则给这条边定向。
当找不到只有一条边仍未被定向的限制时，给当前未定向的编号最小的边定向 $0$ 。

于是现在要做的是“找到只有一条边仍未被定向的限制”，以及“判断是否可以从一个点到达另一个点”。

对于第一个问题考虑倍增优化建图，将一个限制拆成

\log n

个树链。每个树链给限制两个贡献，在这条树链中未被定向的边减到

1

或

0

时减掉一个贡献，当一个限制仅剩一个贡献时加入队列。当处理完

x

点往上一个长度

2^i

的树链后，检查一下与

x

的

2^i

级祖先和

2^i

级后代往上长度

2^i

的树链，看看合成长度

2^{i+1}

的树链后是否需要处理。

对于第二个问题只需要用带权并查集维护一下从

x

点到它当前连通块内祖先的向上、向下的路径条数，再做树上差分即可。然后就能判断一条限制是否需要忽略了。

CPP

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
const int N=5e5+10;
int c,n,m,x[N],y[N],z[N],a[N],b[N],L[N];
int k[N],dep[N],f[N][20],d[N],vis[N][20];
int fa[N],s[N][2];bool F[N];queue <int> q;
vector <int> v[N],e[N][20],g[N][20];
void dfs(int x)
{
    dep[x]=dep[f[x][0]]+1;
    for(int i=1;i<=__lg(dep[x]);++i)
    {
        f[x][i]=f[f[x][i-1]][i-1],vis[x][i]=2;
        e[f[x][i-1]][i-1].push_back(x);
    }
    for(int y:v[x]) if(y!=f[x][0])
        f[y][0]=x,vis[y][0]=1,dfs(y);
}
inline void add(int x,int t,int y)
    {g[x][t].push_back(y),d[y]+=(t?2:1);}
inline int find(int x)
{
    if(fa[x]==x) return x;int fax=find(fa[x]);
    s[x][0]+=s[fa[x]][0],s[x][1]+=s[fa[x]][1];
    return fa[x]=fax;
}
inline void del(int x,int t,int flag)
{
    if(flag>=2) return ;vis[x][t]=flag;
    for(int y:g[x][t]) if(--d[y]==1) q.push(y);
    for(int y:e[x][t]) del(y,t+1,flag+vis[y][t]);
    if(f[x][t+1]) del(x,t+1,flag+vis[f[x][t]][t]);
}
inline void set(int x,int o)
    {z[x]=o,s[x][o]++,del(x,0,0),fa[x]=f[x][0];}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>c>>n>>m;
    for(int i=1;i<=n;++i) fa[i]=i,z[i]=-1;
    for(int i=1;i<n;++i)
    {
        cin>>x[i]>>y[i];
        v[x[i]].push_back(y[i]);
        v[y[i]].push_back(x[i]);
    }
    dfs(1);for(int i=1;i<n;++i)
    {
        F[i]=(f[y[i]][0]==x[i]);
        F[i]?k[y[i]]=0:k[x[i]]=1;
    }
    for(int i=1,x,y;i<=m;++i)
    {
        cin>>x>>y,a[i]=x,b[i]=y;
        if(dep[x]<dep[y]) swap(x,y);
        while(dep[x]>dep[y])
        {
            int t=__lg(dep[x]-dep[y]);
            add(x,t,i),x=f[x][t];
        }
        if(x==y){L[i]=x;continue;}
        for(int j=__lg(dep[x]);~j;--j)
        {
            if(f[x][j]==f[y][j]) continue;
            add(x,j,i),add(y,j,i);
            x=f[x][j],y=f[y][j];
        }
        add(x,0,i),add(y,0,i),L[i]=f[x][0];
    }
    for(int i=1;i<=m;++i) if(d[i]==1) q.push(i);
    for(int o=1;o<n;++o)
    {
        while(!q.empty())
        {
            int p=q.front();q.pop();if(!d[p]) continue;
            int x=find(a[p]),y=find(b[p]),cur=0;
            int len=dep[a[p]]+dep[b[p]]-(dep[L[p]]<<1);
            if(dep[x]<dep[y])
            {
                find(L[p]),find(f[y][0]);
                cur+=(s[a[p]][1]-s[L[p]][1]);
                cur+=(s[f[y][0]][0]-s[L[p]][0])+s[b[p]][0];
                if(cur==len-1) set(y,1);else continue;
            }
            else
            {
                find(L[p]),find(f[x][0]);
                cur+=(s[b[p]][0]-s[L[p]][0]);
                cur+=s[a[p]][1]+(s[f[x][0]][1]-s[L[p]][1]);
                if(cur==len-1) set(x,0);else continue;
            }
        }
        while(o<n&&z[F[o]?y[o]:x[o]]!=-1) ++o;
        F[o]?set(y[o],0):set(x[o],1);
    }
    for(int i=1;i<n;++i)
        cout<<(F[i]?(z[y[i]]==1):(z[x[i]]==0));
    cout<<'\n';return 0;
}

题解：P10787 [NOI2024] 树的定向

文章操作

相关推荐

评论

题解：P10787 [NOI2024] 树的定向