传送门
Description
Solution
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define reg register
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int MN=1e5+5,MM=4e6+5;
int n,m;ll ans;
struct ed{int to,nex;}e[MN<<1];int hr[MN],en;
inline void ins(int x,int y)
{
e[++en]=(ed){y,hr[x]};hr[x]=en;
e[++en]=(ed){x,hr[y]};hr[y]=en;
}
/*------------求lca------------*/
int st[MN<<1][20],eu[MN],id[MN],dfn[MN],pin,dep[MN],fa[MN],dind,lg[MN<<1];
void dfs(int x,int f)
{
id[dfn[x]=++pin]=x;st[dind][0]=x;
eu[x]=++dind;dep[x]=dep[fa[x]=f]+1;
for(int i=hr[x];i;i=e[i].nex)if(e[i].to^f)
st[dind][0]=x,++dind,dfs(e[i].to,x);
}
inline void init()
{
dfs(1,0);register int i,j;
for(i=2;i<=dind;++i)lg[i]=lg[i>>1]+1;
for(j=1;j<20;++j)for(i=1;i<=dind;++i)
{
if(i+(1<<j)>dind) break;
st[i][j]=dep[st[i][j-1]]<dep[st[i+(1<<j-1)][j-1]]?st[i][j-1]:st[i+(1<<j-1)][j-1];
}
}
int LCA(int x,int y)
{
if(!x||!y) return x|y;
if(x==y) return x;
x=eu[x];y=eu[y];if(x>y)swap(x,y);
int b=lg[y-x];
if(dep[st[x][b]]<dep[st[y-(1<<b)][b]])
return st[x][b];
return st[y-(1<<b)][b];
}
/*------------线段树合并------------*/
struct xxx{
int x,y,z;
xxx(int x,int y,int z):x(x),y(y),z(z){}
};
std::vector<xxx> opt[MN];
int ml[MM],mr[MM],ls[MM],rs[MM],v[MM],sum[MM],lca[MM],rt[MN],tot;
void up(int x)
{
ml[x]=ml[ls[x]]?ml[ls[x]]:ml[rs[x]];
mr[x]=mr[rs[x]]?mr[rs[x]]:mr[ls[x]];
v[x]=v[ls[x]]+v[rs[x]];
if(!v[ls[x]]||!v[rs[x]]) sum[x]=sum[ls[x]]+sum[rs[x]];
else sum[x]=sum[ls[x]]+sum[rs[x]]-dep[LCA(id[mr[ls[x]]],id[ml[rs[x]]])];
if(lca[ls[x]]&&lca[rs[x]]) lca[x]=LCA(lca[ls[x]],lca[rs[x]]);
else lca[x]=lca[ls[x]]|lca[rs[x]];
}
int Merge(int x,int y,int l,int r)
{
if(!x||!y) return x|y;
if(l==r)
{
v[x]+=v[y];
if(v[x]) ml[x]=mr[x]=l,lca[x]=id[l],sum[x]=dep[id[l]];
else ml[x]=mr[x]=lca[x]=sum[x]=0;
return x;
}
int mid=(l+r)>>1;
ls[x]=Merge(ls[x],ls[y],l,mid);
rs[x]=Merge(rs[x],rs[y],mid+1,r);
up(x);return x;
}
void Modify(int &x,int l,int r,int a,int b)
{
if(!x) x=++tot;
if(l==r)
{
v[x]+=b;
if(v[x]) ml[x]=mr[x]=l,lca[x]=id[l],sum[x]=dep[id[l]];
else ml[x]=mr[x]=lca[x]=sum[x]=0;
return;
}
int mid=(l+r)>>1;
if(a<=mid) Modify(ls[x],l,mid,a,b);
else Modify(rs[x],mid+1,r,a,b);
up(x);
}
void Solve(int x)
{
register int i;
for(i=hr[x];i;i=e[i].nex)if(e[i].to^fa[x])
Solve(e[i].to),rt[x]=Merge(rt[x],rt[e[i].to],1,n);
for(i=opt[x].size()-1;~i;--i)
Modify(rt[x],1,n,opt[x][i].x,opt[x][i].z),
Modify(rt[x],1,n,opt[x][i].y,opt[x][i].z);
ans+=sum[rt[x]]-dep[lca[rt[x]]];
}
int main()
{
n=read();m=read();
register int i,x,y,z;
for(i=1;i<n;++i) x=read(),ins(x,read());
init();
for(i=1;i<=m;++i)
{
x=read(),y=read();z=LCA(x,y);
opt[x].push_back(xxx(dfn[x],dfn[y],1));
opt[y].push_back(xxx(dfn[x],dfn[y],1));
opt[z].push_back(xxx(dfn[x],dfn[y],-1));
opt[fa[z]].push_back(xxx(dfn[x],dfn[y],-1));
}
ans=0;Solve(1);
return 0*printf("%lld\n",ans>>1);
}
Blog来自PaperCloud，未经允许，请勿转载，TKS！