记录编号	310459	评测结果	AAAAAAAAA
题目名称	暗之链锁	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	1.603 s
提交时间	2016-09-22 16:24:34	内存使用	7.06 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=200100;
vector<int> f[maxn];
int x,y,n,m;
int cnt,deep[maxn],sz[maxn],son[maxn],fa[maxn],top[maxn],id[maxn],T[maxn];
void add(int u,int v)
{
    if(u>v) return;
    ++T[u];--T[v+1];
}
void dfs1(int u,int dep,int fath)
{
    deep[u]=dep;
    sz[u]=1;
    fa[u]=fath;
    for(int i=0;i<f[u].size();i++)
    {
        int v=f[u][i];
        if(v==fath) continue;
        dfs1(v,dep+1,u);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]) son[u]=v;
    }
}

void dfs2(int u,int tp)
{
    //cout<<u<<endl;
    top[u]=tp;
    id[u]=++cnt;
    if(son[u]) dfs2(son[u],tp);
    for(int i=0;i<f[u].size();i++)
    {
        int v=f[u][i];
        if(v!=fa[u]&&v!=son[u])
        dfs2(v,v);
    }
}
void work(int a,int b)
{
    while(top[a]!=top[b])
    {
        if(deep[top[a]]<deep[top[b]]) swap(a,b);
        add(id[top[a]],id[a]);
        a=fa[top[a]];
    }
    if(deep[a]>deep[b]) swap(a,b);
    if(a==b) return;
    add(id[son[a]],id[b]);
}
int main()
{
    freopen("yam.in","r",stdin);
    freopen("yam.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        f[x].push_back(y);
        f[y].push_back(x);
    }
    dfs1(1,-1,0);
    dfs2(1,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        work(x,y);
    }
    T[0]=0;
    for(int i=1;i<=n;i++)
    {
        T[i]+=T[i-1];
    }
    int ans=0;
    for(int i=2;i<=n;i++)
    {
        if(T[i]==1) ++ans;
        else if(T[i]==0) ans+=m;
    }
    printf("%d",ans);
    return 0;
}