C++14(g++5.4) 解法, 执行用时: 546ms, 内存消耗: 31828K, 提交时间: 2019-02-22 20:39:14

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cassert>

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int MAXN=1E5+10;

namespace Segment_Tree{
	int t[MAXN<<3],cov[MAXN<<3];

	void pushup(int x,int l,int r)
	{
		if(cov[x]) t[x]=r-l+1;
		else t[x]=t[x<<1]+t[x<<1|1];
	}

	void change(int x,int l,int r,int cl,int cr,int dlt)
	{
		if(cl<=l&&r<=cr) return cov[x]+=dlt,pushup(x,l,r),void();
		int mid=(l+r)>>1;
		if(cl<=mid) change(x<<1,l,mid,cl,cr,dlt);
		if(cr>mid)  change(x<<1|1,mid+1,r,cl,cr,dlt);
		pushup(x,l,r);
	}
}

struct OPT{
	int x,l,r,f;

	bool operator < (const OPT &rhs) const {return x<rhs.x;}
}op[MAXN*16];

vector<int> T[MAXN];
int cnt,jmp[MAXN][18],dep[MAXN],dfn[MAXN],dft,siz[MAXN],n,m;
ll Ans;

bool inside(int x,int y){return dfn[x]<=dfn[y]&&dfn[y]<=dfn[x]+siz[x]-1;}//y in x

void dfs(int x,int fa)
{
	siz[x]=1;
	dfn[x]=++dft;
	jmp[x][0]=fa;dep[x]=dep[fa]+1;
	for(int v:T[x])
		if(v!=fa)
			dfs(v,x),siz[x]+=siz[v];
}

void solve()
{
	sort(op+1,op+1+cnt);
	for(int i=1;i<=cnt;i++)
	{
		Ans+=1ll*Segment_Tree::t[1]*(op[i].x-op[i-1].x);
		Segment_Tree::change(1,1,n,op[i].l,op[i].r,op[i].f);
	}
}

void add_rec(int x1,int y1,int x2,int y2)
{
	if(x1>x2||y1>y2) return;
	x1=max(1,x1);x1=min(x1,n);
	y1=max(1,y1);y1=min(y1,n);
	x2=max(1,x2);x2=min(x2,n);
	y2=max(1,y2);y2=min(y2,n);
	op[++cnt]=(OPT){x1,y1,y2,1};
	op[++cnt]=(OPT){x2+1,y1,y2,-1};
}

int Nxt(int x,int y)
{
	for(int j=17;~j;j--)
		if(dep[jmp[x][j]]>dep[y])
			x=jmp[x][j];
	return x;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		T[u].push_back(v);
		T[v].push_back(u);
	}
	dfs(1,0);
	for(int j=1;j<=17;j++)
		for(int i=1;i<=n;i++)
			jmp[i][j]=jmp[jmp[i][j-1]][j-1];
	for(int i=1,u,v;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		if(dep[u]>dep[v]) swap(u,v);
		if(inside(u,v))
		{
			int p=Nxt(v,u);
			add_rec(dfn[v],1,dfn[v]+siz[v]-1,dfn[p]-1);
			add_rec(1,dfn[v],dfn[p]-1,dfn[v]+siz[v]-1);
			add_rec(dfn[v],dfn[p]+siz[p],dfn[v]+siz[v]-1,n);
			add_rec(dfn[p]+siz[p],dfn[v],n,dfn[v]+siz[v]-1);
		}
		else
		{
			add_rec(dfn[u],dfn[v],dfn[u]+siz[u]-1,dfn[v]+siz[v]-1);
			add_rec(dfn[v],dfn[u],dfn[v]+siz[v]-1,dfn[u]+siz[u]-1);
		}
	}
	for(int i=1;i<=n;i++) add_rec(i,i,i,i);
	solve();
	printf("%lld\n",(1ll*n*n-Ans)/2);
}

C++11(clang++ 3.9) 解法, 执行用时: 459ms, 内存消耗: 35812K, 提交时间: 2019-03-10 15:09:16

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node
{
	ll sum,cnt;
}tr[400005];
ll n,m,i,u,v,dfn[100005],ed[100005],tot=0,ans=0,dep[100005],nw[100005];
vector<ll> s[100005],ty[100005],x[100005],x2[100005];
bool cmp(ll a,ll b){return dfn[a]<dfn[b];}
void dfs(int p,int f)
{
	ll i,v;
	ed[p]=dfn[p]=++tot;
	dep[p]=dep[f]+1;
	for(i=0;i<s[p].size();i++)
	{
		v=s[p][i];
		if(v==f)continue;
		dfs(v,p);
		ed[p]=ed[v];
	}
}
void upd(int p,int l,int r)
{
	tr[p].sum=0;
	if(tr[p].cnt)tr[p].sum=r-l+1;
	else if(l!=r)tr[p].sum=tr[2*p].sum+tr[2*p+1].sum;
}
void add(int p,int l,int r,int gl,int gr,int v)
{
	int mid;
	if(gl>gr)return;
	if(l>gr||r<gl)return;
	if(l>=gl&&r<=gr)
	{
		tr[p].cnt+=v;
		upd(p,l,r);
		return;
	}
	mid=(l+r)/2;
	add(2*p,l,mid,gl,gr,v);
	add(2*p+1,mid+1,r,gl,gr,v);
	upd(p,l,r);
}
void dfs2(int p,int f)
{
	ll i,j,w,r,hd=0,pre=0;
	nw[dep[p]]=p;
	sort(x2[p].begin(),x2[p].end(),cmp);
	for(i=0;i<x[p].size();i++)
	{
		r=x[p][i];
		add(1,1,n,dfn[r],ed[r],1);
	}
	for(i=0;i<ty[p].size();i++)
	{
		r=nw[ty[p][i]];
		add(1,1,n,1,dfn[r]-1,1);
		add(1,1,n,ed[r]+1,n,1);
	}
	ans+=n-tr[1].sum;
	for(i=0;i<s[p].size();i++)
	{
		w=s[p][i];
		if(w==f)continue;
		while(hd<x2[p].size()&&dfn[x2[p][hd]]>=dfn[w]&&dfn[x2[p][hd]]<=ed[w])
		{
			add(1,1,n,dfn[x2[p][hd]],ed[x2[p][hd]],-1);
			hd++;
		}
		dfs2(w,p);
		for(j=pre;j<hd;j++)
		{
			r=x2[p][j];
			add(1,1,n,dfn[r],ed[r],1);
		}
		pre=hd;
	}
	for(i=0;i<x[p].size();i++)
	{
		r=x[p][i];
		add(1,1,n,dfn[r],ed[r],-1);
	}
	for(i=0;i<ty[p].size();i++)
	{
		r=nw[ty[p][i]];
		add(1,1,n,1,dfn[r]-1,-1);
		add(1,1,n,ed[r]+1,n,-1);
	}
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(i=1;i<n;i++)
	{
		scanf("%lld%lld",&u,&v);
		s[u].push_back(v);
		s[v].push_back(u);
	}
	dfs(1,0);
	for(i=1;i<=m;i++)
	{
		scanf("%lld%lld",&u,&v);
		if(dfn[u]>dfn[v])swap(u,v);
		if(dfn[v]>=dfn[u]&&dfn[v]<=ed[u])
		{
			ty[v].push_back(dep[u]+1);
			x2[u].push_back(v);
			add(1,1,n,dfn[v],ed[v],1);
		}
		else
		{
			x[u].push_back(v);
			x[v].push_back(u);
		}
	}
	dfs2(1,0);
	printf("%lld\n",(ans-n)/2LL);
	return 0;
 }