poj 3417 Network （LCA，路径上有值）

浏览数：48 / 时间：2015年06月09日

题意：

N个点，构成一棵树。给出这棵树的结构。

M条边，(a1,b1)...(am,bm)，代表给树的这些点对连上边。这样就形成了有很多环的一个新”树“。

现在要求你在原树中断一条边，在M条边中断一条边，使得新”树“被分成两个部分。

问有多少种方案。

思路：

连上某条新边（a,b），则必定形成一个环。环的路径是a->...->lca(a,b)->...->b，给这些边的值都加1 。

分情况：

在原树中，若一条边的值>=2，去掉这条边，再去掉M条边中的一条，不影响原树的连通性。方案数为0。

　　　　若一条边的值==1，去掉这条边，必须去掉这条边所在环的那条新边（M条边之一）。方案数为1。

　　　　　若一条边的值==0，去掉这条边，再随意去掉M条边中的一条，都会破坏原树的连通性。方案数为M。

在计算边的值时，采用DP的方式，若要将路径a->...->lca(a,b)->...->b上的边值都加1，则dp[a]++,dp[b]++,dp[lca(a,b)]-=2。

直接看代码。

代码：

int const maxn = 100005;

struct node{
    int to,next,lca;
};

int fa[maxn];
bool vis[maxn];
int head[2*maxn];
int qhead[2*maxn];

node edge[maxn*2];
node qedge[maxn*2];

int n,m,cnt1,cnt2,cn;
int dp[maxn], edgeCount[maxn];


inline void Addedge(int u,int v){
    edge[++cnt1].to=v;
    edge[cnt1].next=head[u];
    head[u]=cnt1;

    edge[++cnt1].to=u;
    edge[cnt1].next=head[v];
    head[v]=cnt1;
}
inline void Addqedge(int u,int v){
    qedge[++cnt2].to=v;
    qedge[cnt2].next=qhead[u];
    qhead[u]=cnt2;

    qedge[++cnt2].to=u;
    qedge[cnt2].next=qhead[v];
    qhead[v]=cnt2;
}
void init(){
    mem(head,-1);  mem(qhead,-1);  mem(vis,false);
    rep(i,1,n) fa[i]=i;
    cnt1=cnt2=0;
}
int findFa(int x){
    return fa[x]==x?x:fa[x]=findFa(fa[x]);
}
void Tarjan_LCA(int u){
    fa[u]=u;
    vis[u]=true;
    for(int i=head[u];i!=-1;i=edge[i].next){
        if(!vis[edge[i].to]){
            Tarjan_LCA(edge[i].to);
            fa[edge[i].to]=u;
        }
    }

    for(int i=qhead[u];i!=-1;i=qedge[i].next){
        if(vis[qedge[i].to])
            qedge[i].lca=findFa(qedge[i].to);
    }
}
int dfsDp(int u,int fa){
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;  if(v==fa) continue;
        int t1=dfsDp(v,u);
        edgeCount[++cn]=t1;
        dp[u]+=t1;
    }
    return dp[u];
}


int a,b;
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        rep(i,1,n-1){
            scanf("%d%d",&a,&b);
            Addedge(a,b);
        }
        mem(dp,0);
        rep(i,1,m){
            scanf("%d%d",&a,&b);
            Addqedge(a,b);
            dp[a]++;  dp[b]++;
        }
        Tarjan_LCA(1);
        for(int i=1;i<=cnt2;i+=2){
            dp[qedge[i].lca]-=2;
        }
        mem(edgeCount,0);
        cn=0;
        dfsDp(1,-1);
        int ans=0;
        rep(i,1,cn){
            if(edgeCount[i]==1)
                ans++;
            else if(edgeCount[i]==0)
                ans+=m;
        }
        printf("%d\n",ans);
    }
}