A-小王子

给你 个点， 条白边， 条黑边，问删去 条白边， 条黑边可以把树恰好分为两部分的方案数

对每条白边来说：（删这个白边）

1.这个白边属于一个环，那么删掉构成环的黑边：种方案；
2.这个白边属于多个环，那么删一条黑边无用： 种方案
3.这个白边不在环上，那么可以删除任意一条黑边， 种方案。
怎么判断环：每条黑边 求 , 那么利用树上的差分 代表这个点上方的边所在环的数目。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 5;
inline int read(){
    int x = 0;char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
struct edge{int to,next;}e[N<<1]; int head[N],tot;
inline void add(int u,int v){
    e[++tot] = (edge){v,head[u]}; head[u] = tot;
}
int dep[N],siz[N],fa[N],son[N]; long long ans;
void dfs1(int x,int ff){
    dep[x] = dep[ff] + 1; siz[x] = 1; fa[x] = ff;
    for(int i = head[x];i;i = e[i].next){
        int v = e[i].to;
        if(v == ff) continue;
        dfs1(v,x); siz[x] += siz[v];
        if(siz[son[x]] < siz[v]) son[x] = v;
    }
}
int top[N],cha[N],n,m;
void dfs2(int x,int tp){
    top[x] = tp;
    if(son[x]) dfs2(son[x],tp);
    for(int i = head[x];i;i = e[i].next){
        int v = e[i].to;
        if(v == fa[x] || v == son[x]) continue;
        dfs2(v,v);
    }
}
inline int lca(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])
            swap(x,y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
void dfs3(int x){
    for(int i = head[x];i;i = e[i].next){
        int v = e[i].to;
        if(v == fa[x]) continue;
        dfs3(v); cha[x] += cha[v];
    }
    if(x > 1){
        if(!cha[x]) ans += m;//不属于任何环
        else if(cha[x] == 1) ++ans;//属于1个环 
    }
}
int main(){
    n = read(); m = read();int u,v;
    for(int i = 1;i < n;++i){
        u = read(); v = read();
        add(u,v); add(v,u);
    }
    dfs1(1,0); dfs2(1,1);
    for(int i = 1;i <= m;++i){
        u = read(); v = read();
        ++cha[u]; ++cha[v]; cha[lca(u,v)] -= 2;
    }
    dfs3(1); printf("%lld",ans);
}