很难的一个题目(对我这种图论蒟蒻来说).首先你得会的算法有:lca,dfs(居然没了...
这个题的解法分为三步:
1.转化题意:原本的题意是给你n个点,m条边,前n-1条是树边,后面的边和树边可以形成多少个环?->成环可以转化为,a->b的路径和c->d的路径有交集.我们去掉交集就是环.
2.计数:直接计数无从下手,我们不妨利用拆边的方式计数,把原本的a->b拆成a->lca(a,b),b->lca(a,b).再分别计数,计数可以采用树上前缀和的形式.把sum[a]++,sum[b]++,用个dfs统计根到a,b的sum[a],sum[b].最后拿sum[a]+sum[b]-2*sum[lca(a,b)]即可.
3.去重:这样计数会存在两种重复的形式,第一种是你拆边的时候拆成2条边,假如另外2条边和这两条边路径在两侧重叠,明显答案是1的,你就会统计成2,假如3条边是这样,那么你就会统计成6,但是只有3,如此可以采用算出距离lca最近的两个点来进行判断即可.另外一种重叠在我统计sum[a]和sum[b]的时候,我们容易发现当多个sum[a]重合的时候,并不是每次都把他们的值统计,而是第一次统计0,第二次统计1,最后统计n-1.也可以用一种方法去重,至此这个题目思路就完成了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=20;
int fa[N][M];
int sum[N],a[N],b[N],dep[N];
vector<int>v[N];
void init(int u,int f,int depth)
{
    fa[u][0]=f;dep[u]=depth;
    for(int i=1;(1<<i)<=depth;i++)
    {
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i];
        if(f==x) continue;
        init(x,u,depth+1);
    }
}

int lca(int u1,int u2)
{
    if(dep[u2]>dep[u1]) swap(u1,u2);//u2µÄÉî¶ÈС¡£
    for(int i=18;i>=0;i--)
    {
        if(dep[fa[u1][i]]>=dep[u2]) u1=fa[u1][i];
    }
    if(u1==u2) return u1;
    for(int i=18;i>=0;i--)
    {
        if(fa[u1][i]!=fa[u2][i])
        {
            u1=fa[u1][i];
            u2=fa[u2][i];
        }
    }
    return fa[u1][0];
}

int close(int u,int anc)
{
    if(u==anc) return -1;
    for(int i=18;i>=0;i--)
    {
        if(dep[fa[u][i]]>dep[anc])
        {
            u=fa[u][i];
        }
    }
    return u;
}

void dfs(int u,int f)
{
    sum[u]+=sum[f];
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i];
        if(x==f) continue;
        dfs(x,u);
    }
}
map<int,int>mp[N];
int main()
{
    int n,m;long long ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    init(1,0,1);
    for(int i=n;i<=m;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        int anc=lca(a[i],b[i]);
        int ca=close(a[i],anc);
        int cb=close(b[i],anc);
        if(ca!=-1)
        {
            sum[ca]++;
            ans-=sum[ca];
        }
        if(cb!=-1)
        {
            sum[cb]++;
            ans-=sum[cb];
        }
        if(cb!=-1&&ca!=-1)
        {
            if(cb>ca) swap(ca,cb);
            ans-=mp[ca][cb];
            mp[ca][cb]++;
        }
    }
    dfs(1,0);
    //cout<<ans<<endl;
    for(int i=n;i<=m;i++)
    {
        ans+=sum[a[i]]+sum[b[i]]-2*sum[lca(a[i],b[i])];
    }
    printf("%lld\n",ans);
    return 0;
}

数据要开long long 不然就7分/...