POJ 3417 Network

题目链接http://poj.org/problem?id=3417

题意:略。

思路:头一次见到卡vector的题目。。。烦躁。。由题意我们可以知道主要边组成了一棵树,附加边是非树边,把一个附加边(x,y)加到树中会与树上x,y之间的路径形成一个环,这时候如果我们砍掉环上的树边,那么我们第二条肯定要砍掉这个附加边才能使这个图变成不连通的两部分,所以我们只要统计每条树边在几个环里就可以了。如果没在环里,那么方案数就加上附加边数,如果在一个环里,那只能砍掉那个特定的附加边才行,方案数加一,如果大于等于两个环肯定没有办法。如果存在附加边(x,y),那么我们把从xy的路径上加一即可,最后看树边上的数值就知道这条树边在几个环里了,解决这个用树上差分就可以了。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mp make_pair
#define ALL(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
template <class T1, class T2>inline void gmax(T1 &a,T2 b){if (b>a) a=b;}
template <class T1, class T2>inline void gmin(T1 &a,T2 b){if (b<a) a=b;}
const int N=100000+10;
int n,m,i,a,b,cnt,ans,dep[N],sz[N],son[N],bel[N],fa[N],sum[N],head[N*2],nxt[N*2],to[N*2];
void dfs1(int u,int f){
    fa[u]=f;
    dep[u]=f?dep[f]+1:0;
    sz[u]=1;
    son[u]=-1;
    for (int i=head[u];~i;i=nxt[i]){
        int v=to[i];
        if (v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1 || sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int f){
    bel[u]=f;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=head[u];~i;i=nxt[i]){
        int v=to[i];
        if (v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v){
    for (;bel[u]!=bel[v];dep[bel[u]]>dep[bel[v]]?u=fa[bel[u]]:v=fa[bel[v]]);
    return dep[u]<dep[v]?u:v;
}
void dfs(int u,int f){
    for (int i=head[u];~i;i=nxt[i]){
        int v=to[i];
        if (v==f) continue;
        dfs(v,u);
        sum[u]+=sum[v];
    }
    if (u==1) return;
    if (sum[u]==0) ans+=m;
    else if (sum[u]==1) ans++;
}
void add(int u,int v){
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt++;
}
int main(){
    read(n),read(m);
    memset(head,-1,sizeof(head));
    for (i=1;i<n;i++){
        read(a),read(b);
        add(a,b);
        add(b,a);
    }
    dfs1(1,0);
    dfs2(1,1);
    for (i=1;i<=m;i++){
        read(a),read(b);
        int p=lca(a,b);
        sum[a]++,sum[b]++,sum[p]-=2;
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注