poj3417lca+树上差分

/*

给定n个点的树，在其中加入m条新边（称为非树边）

现在可以割断一条树边，一条非树边，使图分裂成两个联通块，请问有几种切割方式

对树边进行分情况讨论

    如果树边不处在环中，则割断这条树边后可以割断任意条非树边

    如果树边仅仅被一个环包含，则割断这条树边后只能割断一条非树边，即环中的那条非树边

    如果树边被两个及以上环包含，就不可能有合法的切割方式

那么考虑如何计算树边被多少个环包含

    显然每次加入一条非树边（x，y），x->lca(x,y)->y->x就会形成一个环

    如果第一次割断这个环上的边，那么第二次就必须割断（x，y）

注意这里的环仅仅指的是非树边沿着两段向上覆盖的环

    那么每次加入一条非树边（x，y），就找到lca(x,y)，x->lca->y路径上的所有边权+1

如何将路径上所有边权+1：使用树上差分即可，仅仅操作lca，x，y三个点的权值即可

最后枚举每一条边，分类考虑边权=0,1,2的三种情况并求和即可

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#include<cmath>

using namespace std;

#define maxn 200005

struct Edge{int to,nxt;}edge[maxn<<];

int head[maxn],tot,n,m,cnt[maxn];

void init(){

    memset(head,-,sizeof head);

    tot=;

}

void addedge(int u,int v){

    edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;

}

int f[maxn][],d[maxn],t;

void bfs(){

    queue<int>q;

    q.push();d[]=;

    while(!q.empty()){

        int u=q.front();q.pop();

        for(int i=head[u];i!=-;i=edge[i].nxt){

            int v=edge[i].to;

            if(d[v])continue;

            f[v][]=u;

            d[v]=d[u]+;

            for(int k=;k<=;k++)

                f[v][k]=f[f[v][k-]][k-];

            q.push(v);

        }

    }

}

int lca(int x,int y){

    if(d[x]<d[y])swap(x,y);

    for(int i=;i>=;i--)

        if(d[f[x][i]]>=d[y])x=f[x][i];

    if(x==y)return y;

    for(int i=;i>=;i--)

        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];

    return f[x][];

}

long long ans;

void dfs(int u,int pre){

    for(int i=head[u];i!=-;i=edge[i].nxt){

        int v=edge[i].to;

        if(v==pre)continue;

        dfs(v,u);

        cnt[u]+=cnt[v];

    }

}

int main(){

    init();

    cin>>n>>m;

    for(int i=;i<n;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        addedge(u,v);addedge(v,u);

    }

    bfs();

    for(int i=;i<=m;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        cnt[lca(u,v)]-=;

        cnt[u]++;cnt[v]++;

    }

    dfs(,);

    for(int i=;i<=n;i++)

        if(cnt[i]==)ans+=m;

        else if(cnt[i]==)ans++;

    cout<<ans<<endl;

}