记录编号	428898	评测结果	AAAAAAAAA
题目名称	暗之链锁	最终得分	100
用户昵称	Troywar	是否通过	通过
代码语言	C++	运行时间	0.355 s
提交时间	2017-07-26 14:09:04	内存使用	9.85 MiB

#include<cstdio>
#include<iostream>
long long ans;
inline int read(){
    int s=0;char ch=getchar();
    while(ch<'0'||ch>'9')   ch=getchar();
    while(ch>='0'&&ch<='9') s=s*10+ch-48,ch=getchar();
    return s;
}
const int N=100010;
struct edges{
    int v;edges *last;
}edge[N<<1],*head[N];int cnt;
inline void push(int u,int v){
    edge[++cnt].v=v;edge[cnt].last=head[u];
    head[u]=edge+cnt;
}
int f[N][18],dep[N];
void dfs(int x){
    for(int i=1;(1<<i)<=dep[x];i++)
        f[x][i]=f[f[x][i-1]][i-1];
    for(edges *i=head[x];i;i=i->last){
        if(i->v!=f[x][0]){
            dep[i->v]=dep[x]+1;
            f[i->v][0]=x;
            dfs(i->v);
        }
    }
}
int tmp[N];
inline int lca(int x,int y){
    if(dep[x]<dep[y])   std::swap(x,y);
    int t=dep[x]-dep[y];
    for(int i=0;t;i++)
        if(t&(1<<i)){
            t-=(1<<i);
            x=f[x][i];
        }
    if(x==y)    return x;
    for(int i=16;i>=0;i--){
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}
int n,m;
void _dfs(int x){
    for(edges *i=head[x];i;i=i->last){
        if(i->v==f[x][0])   continue;
        _dfs(i->v);
        tmp[x]+=tmp[i->v];
    }
}
int main(){
    freopen("yam.in","r",stdin);
    freopen("yam.out","w",stdout);
    n=read(),m=read();
    for(int i=1,u,v;i<n;i++){
        u=read(),v=read();
        if(u==v)    continue;
        push(u,v),push(v,u);
    }
    dfs(1);
    for(int i=1,u,v;i<=m;i++){
        u=read(),v=read();
        int t=lca(u,v);
        tmp[u]++;
        tmp[v]++;
        tmp[t]-=2;
    }
    _dfs(1);
    for(int i=2;i<=n;i++){
        if(tmp[i]==0)   ans+=m;
        if(tmp[i]==1)   ans++;
    }
    printf("%lld\n",ans);
}