POJ 3417 Network

作者: MayFlyyh 分类: LCA 发布时间: 2018-08-11 16:11 ė 6 没有评论

题意:给你一颗N个节点树,再给你M条新边(保证不与树边重复)。现在求剪短一条树边和任意M边中的一条边,能将树分成两个联通块的方案

> N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ 100 000)

一开始想的:暴力,N*M然后检验。。

然后想到树形DP,能不能按照每个节点剪掉它与它父亲节点的树边思考

剪掉这条树边,树边部分肯定不与大树相连接

分类讨论一下新边:

1.如果该子树内任意节点不与大树有新边,那么剪掉任意一条新边都可以产生两个联通块,方案数+M

2.如果该子树内有且仅有1个节点与大树有新边,那么剪掉该边即可产生两个联通块,方案数+1

3.如果该子树内有2个或以上节点与大树有新边,不可能的

问题就是怎么算每一个子树内与树外连接的新边数量

我们发现,两个节点在同子树内,且子树根结点离根节点最远时(最小子树),那么该节点必是两个节点的lca。

设a[i]为以i为根结点连接子树外的新边数量

所以每次连新边的时候,a[x]++,a[y]++,a[lca(x,y)]-=2

然后dfs把每个子树累加

CODE:

#include<iostream>
#include<cstdio>
typedef long long ll;
const int N = 100100;
struct edge{
    int next,to;
}e[N<<1];
int last[N],top[N],m,size[N],wson[N],D[N],fa[N];
int cnt;ll dp[N];ll ans=0;
inline void add(int a,int b){
    cnt++;
    e[cnt].to=b;e[cnt].next=last[a],last[a]=cnt;
}
inline int read(){
    int x=0,flag=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*flag;
}
inline int dfs1(int x,int f){
    size[x]=1;
    D[x]=D[f]+1;
    fa[x]=f; 
    for(int i=last[x];i;i=e[i].next){
        if(e[i].to==f) continue;
        dfs1(e[i].to,x);
        size[x]+=size[e[i].to]; 
        if(size[e[i].to]>size[wson[x]]) wson[x]=e[i].to;
    }
    return 0;
}
inline int dfs2(int x,int topf){
    top[x]=topf;
    if(!wson[x]) return 0;
    dfs2(wson[x],topf);
    for(int i=last[x];i;i=e[i].next){
        if(e[i].to==fa[x]) continue;
        if(e[i].to==wson[x]) continue;
        dfs2(e[i].to,e[i].to);
    }
    return 0;
}
inline int lca(int x,int y){
    while(top[x]!=top[y]){
        if(D[top[x]]<D[top[y]]) std::swap(x,y);
        x=fa[top[x]];
    }
    return D[x]>D[y]?y:x;
}
inline int dfs(int x){
    for(int i=last[x];i;i=e[i].next){
        if(e[i].to==fa[x]) continue;
        dfs(e[i].to);
        dp[x]+=dp[e[i].to];
    }
    if(!dp[x]&&fa[x]) ans+=m; 
    if(dp[x]==1) ans++;
    return 0;
}
int main(){
    int n=read();m=read();
    for(int i=1;i<=n-1;++i){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=m;++i){
        int a=read(),b=read();
        int LCA=lca(a,b);
        dp[a]++,dp[b]++,dp[LCA]-=2;
    }
    dfs(1);
    printf("%lld",ans);
    return 0;
}


本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/303

0

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部