POJ 3417 Network

题解 数据结构-树链剖分 图论-LCA
题目链接 编辑文章

题意

给一棵有 $n$ 个节点的树,然后再连 $m$ 条不重合的附加边,可以删除一条树边和一条附加边,问有多少种删除方法可以使树断裂。

题解

显然,每次加一条边以后树上一定会形成环,这个环任意断附加边就可以形成树,而树上任意断一条边就可以使树断裂。

但是有可能会形成很多有重叠部分的环,这样按照上述方法不一定可以让树断裂。

所以我们可以对每一条树边 $i$ 记录包含它的环的个数 $f[i]$ ,然后进行分类讨论:

所以我们可以用 $f[i]$ 表示 $i$ 与父节点之间的边被环包含的次数,然后进行分类讨论:

  1. $f[i]=0$ ,删掉这条边树就断裂了,然后删任意附加边都可以,对答案贡献 $m$ 。
  2. $f[i]=1$ ,删掉这条边还要删去构成这个环的附加边,对答案贡献 $1$
  3. $f[i]>1$ ,删掉这条边后无论怎么删都不能使树断裂了,对答案贡献 $0$

统计 $f[i]$ 可以用一个类似差分的方法:对于每次输入的附加边 $(a,b)$ ,我们对 $f[a]++,f[b]++,f[lca(a,b)]-=2$ ,最后跑一遍 $dfs$ 就可以得到 $f[i]$:

$$f[i]+=f[j] , j\in son[i]$$

最后的答案就是所有边的 $f[i]$ 之和。

求 $lca$ 我还是照样用树剖,还冲到了榜第 $5$ ,树剖果然是求 $lca$ 最好的算法。

struct Edge{
    int next,to;
} edge[200005];
int n,m,a,b,cnt,ans,head[100005],fa[100005],son[100005],siz[100005],top[100005],deep[100005],f[100005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs1(int x,int f,int dep)
{
    fa[x]=f;
    deep[x]=dep;
    siz[x]=1;
    int mx=0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs1(y,x,dep+1);
        siz[x]+=siz[y];
        if (siz[x]>mx)
        {
            mx=siz[x];
            son[x]=y;
        }
    }
}

void dfs2(int x,int topf)
{
    top[x]=topf;
    if (!son[x]) return;
    dfs2(son[x],topf);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}

inline int get_lca(int u,int v)
{
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    return u;
}

void dfs3(int x)
{
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa[x]) continue;
        dfs3(y);
        f[x]+=f[y];
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        f[a]++; f[b]++; f[get_lca(a,b)]-=2;
    }
    dfs3(1);
    for (int i=2;i<=n;i++) ans+=!f[i] ? m : f[i]==1 ? 1 : 0;
    printf("%d",ans);
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。