Dark chain lock (lca+ difference on tree)

subject

The legendary dark chain is called $Dark$.

$Dark$ It is the product of the darkness of the human heart , Brave men at all times and in all countries tried to bring it down .

After study , Have you found $Dark$ Present the structure of an undirected graph , The picture shows $N$ Two nodes and two kinds of edges , One kind of edge is called main edge , The other kind is called additional edge .

$Dark$ Yes $N–1$ The first major edge , also $Dark$ There is a path composed of only the main edges between any two nodes of .

in addition ,$Dark$ also $M$ Additional edges .

Your task is to bring $Dark$ Cut into two disconnected parts .

In limine $Dark$ The additional edges of the are invincible , You can only choose one main edge to cut .

Once you cut off a major side ,$Dark$ Will enter defense mode , The main edge will become invincible and the additional edge can be cut off .

But your ability can only be cut off again $Dark$ An additional edge of .

Now you want to know , How many options can defeat $Dark$.

Be careful , Even if you cut off the main side in the first step, you have already $Dark$ Cut into two pieces , You also need to cut off an additional edge to defeat $Dark$.

Input format
The first line contains two integers $N$ and $M$.

after $N–1$ That's ok , Each line contains two integers $A$ and $B$, Express $A$ and $B$ There is a main side between .

after $M$ Lines give additional edges in the same format .

Output format
Output an integer for the answer .

Data range
$N\le 100000$,$M\le 200000$, The data guarantee that the answer is no more than $2^{31}-1$
sample input ：

4 1
1 2
2 3
1 4
3 4

sample output ：

3

LCA+ The difference in the tree

The topic is that let's delete a main edge and an additional edge to change the graph into two parts

$1.fromOntoOutOfchartYesnindividualspot、n-1stripLordwantedge、mstripattachAddedgeandAndrenIt\; meanstwospotAndbetweenallfromLordwantedgephaseeven,saybrightThechartyesfromLordwantedgestructurebecomeOfOneTreeTrees$

$2.xToyOfroadpathinOfattachAddedge<=1onlycanWithholdchartchangebecometwoMinistrybranch(byWhatWell？：becausebyLordwantedgehasthestructurebecome了OnestarTrees,Such\; asfruitsometwospotroadpathinsavestayOnestripWithOnOfattachAddedge,besaybrightDeletefallOnestripattachAddedge,ItsHeThe\; earthFangalsoyeseventhroughOf,JustNocanholdchartchangebytwoMinistrybranch)$

$3.Need\; to\; bewantsystemmeterTheroadpathinYesmanyLessstripattachAddedge.TheSuch\; asWhatCome\; onIt\text{'}s\; aboutThe\; reason\; isroadpathinattachAddedgeOfindividualCountWell？—>TreesOnBadbranch$

$4.TreesOnBadbranch：Such\; asfruitWant\; toGive\; WayxandyAndbetweenOfroadpathOnAddOnOneindividualCountcandAndNoshadowringItsHeroadpathOfjunctionfruit：x+=c,y+=c,lca(x,y)-=2\ast c.【lca(x,y)yesxandyOfmostnearMalecommonAncestorFirst】$

$5.3、\; ...\; andKind\; oflovecondition：(roadpathinpowervalueusedCome\; onsurfacein、ansgenerationsurfaceanswercase)$
(1)d=0： After cutting off the main side , No matter which additional edge is cut , The picture is still in two parts , So there is m Medium scheme —>ans+=m;

(2)d=1： After cutting off the main side , The additional edge must be cut off to make the graph become two parts , So there is only one solution —>ans++

(3)d>=2： After cutting off the main side , No matter which additional edge is cut, the graph cannot be changed into two parts , So this plan is not feasible —>ans+=0

AC Code （C++）

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const int N=100010,M=N<<1;

int depth[N];  // The depth of each point 
bool st[N];
int n,m;
int f[N][20];  //f[i][j]:i A little jump j Points reached 
int h[N],e[M],ne[M],idx;
int s[N];   // The prefix and 
int ans;

void add(int a,int b){
    
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

// Preprocess the depth of each point and jump of each point k The next point you can jump to 
void bfs(){
    
    queue<int> q;
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[1]=1;
    q.push(1);
    st[1]=true;
    
    while(q.size()){
    
        int t=q.front();
        q.pop();
        st[t]=false;
        
        for(int i=h[t];i!=-1;i=ne[i]){
    
            int j=e[i];
            if(depth[j]>depth[t]+1){
    
                depth[j]=depth[t]+1;
                f[j][0]=t;
                for(int k=1;k<=16;k++){
    
                    f[j][k]=f[f[j][k-1]][k-1];
                }
                
                if(!st[j]){
    
                    st[j]=true;
                    q.push(j);
                }
                
            }
        }
    }
}

// Recent public ancestor 
int lca(int a,int b){
    
    if(depth[a]<depth[b]) swap(a,b);
    // Different depths 
    for(int k=16;k>=0;k--){
    
        if(depth[f[a][k]]>=depth[b]){
    
            a=f[a][k];
        }
    }
    
    if(a==b) return a;
    // If it doesn't return , That explains. a and b Already on the same floor 
    for(int k=16;k>=0;k--){
    
        if(f[a][k]!=f[b][k]){
    
            a=f[a][k];
            b=f[b][k];
        }
    }
    return f[a][0];  // here a and b Not to the nearest public ancestor , Need to jump once 
}

int dfs(int u,int fa){
    
    int res=s[u];
    
    for(int i=h[u];i!=-1;i=ne[i]){
    
        int j=e[i];
        if(j==fa) continue;
        int t=dfs(j,u);
        if(t==0) ans+=m;
        else if(t==1) ans++;
        res+=t;
    }
    return res;
}

int main(){
    
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++){
    
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    
    bfs();
    
    for(int i=1;i<=m;i++){
    
        int a,b;
        scanf("%d%d",&a,&b);
        int t=lca(a,b);
        s[a]++,s[b]++,s[t]-=2;
    }
    
    dfs(1,-1);
    
    printf("%d",ans);
    return 0;
    
}