Network POJ - 3417 lca+ dfs

參考http://blog.csdn.net/l123012013048/article/details/47738691

照着别人的代碼，

1. 這個地方的用數組實作隊列挺好的這樣，就可以從葉子開始到根了
2. 這個地方的 小技巧應該比較普遍吧，dp【u】++，dp【v】++，dp【lca】-=2；

https://vjudge.net/contest/51670#rank

int tot,fst[N],vv[N<<],nxt[N<<];
int dep[N],dp[N];
int fa[][N];
int n,m;

void add(int u,int v ){
    vv[tot]=v,nxt[tot]=fst[u];fst[u]=tot++;
}
void init(){
    mem(fst,-);tot=;mem(dep,);mem(dp,);
}
int lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    for(int k=;k>=;--k){
        if((dep[v]-dep[u])>>k&)v=fa[k][v];
    }
    if(u==v)return u;
    for(int k=;k>=;--k){
        if(fa[k][u]!=fa[k][v])
            u=fa[k][u], v=fa[k][v];
    }
    return fa[][u];
}
int q[N];
void lca_init(){
    dep[]=;
    int head=,tail=;
    q[1]=;
    fa[][]=-;
    while(head<=tail){
        int u=q[head++];
        for(int i=fst[u];~i;i=nxt[i]){
            int v=vv[i];
            if(v==fa[][u])continue;
            fa[][v]=u;
            dep[v]=dep[u]+;
            q[++tail]=v;
        }
    }
    for(int k=;k<;++k){
        for(int i=;i<=n;++i){
            if(fa[k][i]==-)fa[k+][i]=-;
            else fa[k+][i]=fa[k][fa[k][i]];
        }
    }
}
void read(){
    init();
    int u,v;
    rep(i,,n-)sf("%d%d",&u,&v),add(u,v),add(v,u);
    lca_init();
    rep(i,,m){sf("%d%d",&u,&v);dp[u]++;dp[v]++;dp[lca(u,v)]-=;}
}
int main(){
    //freopen("in.txt","r",stdin);
    while(~sf("%d%d",&n,&m)){
        read();
        LL ans=;
        for(int i=n;i>=;--i){
            int v=q[i];
            dp[fa[][v]]+=dp[v];
        }
        for(int i=;i<=n;++i){
            if(dp[i]==)ans+=m;
            else if(dp[i]==)ans++;
        }
        cout<<ans<<'\n';
    }
}