【题解】 CF1268E Happy Cactus

seztto · 2022-02-14 11:10:06 · 题解

题意

给定一颗仙人掌，每条边有边权且边权互不相同。

定义一条路径 (u,v) 合法当且仅当该路径边权递增。

对于每个点 u ，求出存在路径 (u,v) 合法的 v 的个数。

分析

考虑特殊情况，当仙人掌退化为树时，有一个显然的 O(n) 做法，将边按照边权从大到小的顺序加入，定义 f_i 为当前图点 i 的答案。那么当加入一条边 (u,v) 时，u 可以通过该边到达 v 及 v 原本能到达的点，v 同理。即：

然后考虑仙人掌，同样从大到小插边，当加入边 (u,v) 时，u 可以通过该边到达 v 及 v 原本能到达的点。但是，因为仙人掌上有环，有可能有些点被数重了，像这样：

先插入边 (1,3) ，答案变为 {\{3\},\varnothing,\{1\}} 。

然后插入边 (2,3) ，答案变为 {\{3\},\{1,3\},\{2,3\}} 。

最后插入边 (1,2) ，答案变为 {\{2,3\},\{1,3\},\{1,2\}} 。

我们发现在插入红边时两边的点答案有重复，这时要去重。

归纳发现，当且仅当在插入一个最小边能通过环的两边合法地到达最大边环的最后一条边时，该环的最大边对最小边的两个点都有贡献，此时减去最大边对最小边的贡献（插入最大边时最大边的答案）即可。即：（记最大边的其中一个点为 x ）

因为点 x 的贡献可能会变化，所以这里用 g_x 表示插入最大边时 x 的答案。

总结

没有什么坑点，写对点双就可以了。

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<ctime>
using namespace std;
vector <int> edge[1000005],_time[1000005];
stack <int> sta;
int n,m,x,y,cnt,low[1000005],dfn[1000005],color,col[1000005],maxa,mina,f[1000005],g[1000005],lk[1000005],head[1000005];
struct data
{
    int x,y;
}E[1000005];
void tarjan (int x,int y)
{
    sta.push(x);
    low[x]=dfn[x]=++cnt;
    int len=edge[x].size();
    for (int i=0;i<len;i++)
    {
        if (edge[x][i]==y)
            continue;
        if (dfn[edge[x][i]])
            low[x]=min(low[x],dfn[edge[x][i]]);
        else
        {
            tarjan(edge[x][i],x);
            low[x]=min(low[x],low[edge[x][i]]);
            if (dfn[x]<=low[edge[x][i]])
            {
                int z=sta.top();
                sta.pop();
                color++;
                col[z]=color;
                while (z!=edge[x][i])
                {
                    z=sta.top();
                    sta.pop();
                    col[z]=color;
                }
                head[color]=x;
            }
        }
    }
    return ;
}
void dfs (int x,int y,int z)
{
    int len=edge[x].size();
    bool f=false;
    for (int i=0;i<len;i++)
    {
        if (edge[x][i]==y)
            continue;
        if (col[edge[x][i]]!=z)
            continue;
        maxa=max(maxa,_time[x][i]);
        mina=min(mina,_time[x][i]);
        if (!f)
        {
            dfs(edge[x][i],x,z);
            f=true;
        }
    }
    return ;
}
int ck (int x,int y,int z,int c)
{
    // cout<<x<<' '<<y<<' '<<z<<endl;
    int len=edge[x].size();
    for (int i=0;i<len;i++)
    {
        if ((head[c]!=edge[x][i]&&c!=col[edge[x][i]])||edge[x][i]==y)
            continue;
        if (_time[x][i]>z)
            continue;
        return ck(edge[x][i],x,_time[x][i],c);
    }
    return z;
}
bool check (int k,int z)
{
    x=E[k].x;
    // cout<<x<<endl;
    int len=edge[x].size();
    bool f=true;
    for (int i=0;i<len;i++)
        if (col[edge[x][i]]==z||edge[x][i]==head[z])
            f&=(ck(edge[x][i],x,_time[x][i],z)==mina);
    return f;
}
int main ()
{
    // freopen("data.in","r",stdin);
    // freopen("3.out","w",stdout);
    // cerr<<CLOCKS_PER_SEC<<endl;
    // long t1=clock();
    // cerr<<t1<<endl;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        edge[x].push_back(y);
        _time[x].push_back(i);
        edge[y].push_back(x);
        _time[y].push_back(i);
        E[i]=data{x,y};
    }
    tarjan(1,0);
    // for (int i=1;i<=n;i++)
    //  cout<<col[i]<<' ';
    // cout<<endl;
    // for (int i=1;i<=color;i++)
    //  cout<<head[i]<<' ';
    // cout<<endl;
    for (int i=1;i<=color;i++)
    {
        mina=m;
        maxa=0;
        dfs(head[i],0,i);
        // cout<<mina<<' '<<maxa<<endl;
        if (mina!=maxa&&check(maxa,i))
        {
            lk[mina]=maxa;
            // cout<<mina<<' '<<maxa<<endl;
        }
    }
    // for (int i=1;i<=n;i++)
    //  f[i]=1;
    for (int i=m;i>=1;i--)
    {
        x=E[i].x;
        y=E[i].y;
        f[x]=f[y]=f[x]+f[y]+1-g[lk[i]];
        g[i]=f[x]+1;
        // cout<<x<<' '<<y<<' '<<f[y]<<endl;
    }
    for (int i=1;i<=n;i++)
        printf("%d ",f[i]);
    // double t2=clock();
    // cerr<<t2-t1;
    return 0;
}