【GOJ 3007】树

题目

正解

两条树链的交显然也是一条链。链有一个很好的性质：链上的点数(-)链上的边数(=1)。所以如果一对链在同一个点上出现，答案(+1)；在同一条边上出现则答案(-1)，这样就可以得到最终的答案。在求出一条链的(lca)后，可以树上差分快速求出每个点、每条边被多少条链覆盖，进而求出最终答案。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5+2;
struct edge {
	LL to,nxt,w;
} e[N*5];
LL n,m,head[N],cnt;
void add(LL u,LL v) {
	e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
LL dep[N],f[N][25];
void build(LL u,LL fa) {
	dep[u]=dep[fa]+1;
	for(LL i=1; (1<<i)<=dep[u]; i++) {
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(LL i=head[u]; i; i=e[i].nxt) {
		LL v=e[i].to;
		if(fa==v) {
			continue;
		}
		f[v][0]=u,build(v,u);
	}
}
LL lca(LL x,LL y) {
	if(dep[x]<dep[y]) {
		swap(x,y);
	}
	for(LL i=22; i>=0; i--) {
		if(dep[f[x][i]]>=dep[y]) {
			x=f[x][i];
		}
		if(x==y) {
			return x;
		}
	}
	for(LL i=22; i>=0; i--) {
		if(f[x][i]^f[y][i]) {
			x=f[x][i],y=f[y][i];
		}
	}
	return f[x][0];
}
struct lian {
	LL u,v,hrq;
} lsc[N];
LL sum[N];
void dfs(LL u,LL fa) {
	for(LL i=head[u]; i; i=e[i].nxt) {
		LL v=e[i].to;
		if(v==fa) {
			continue;
		}
		sum[v]+=sum[u];
		dfs(v,u);
	}
}
int main() {
	scanf("%lld %lld",&n,&m);
	for(LL i=1,u,v; i<n; i++) {
		scanf("%lld %lld",&u,&v),add(u,v),add(v,u);
	}
	build(1,0);
	for(LL i=1; i<=m; i++) {
		scanf("%lld %lld",&lsc[i].u,&lsc[i].v);
		if(lsc[i].u>lsc[i].v) {
			swap(lsc[i].u,lsc[i].v);
		}
		lsc[i].hrq=lca(lsc[i].u,lsc[i].v),sum[lsc[i].hrq]++;
	}
	LL ans=0;
	for(LL i=1; i<=n; i++) {
		ans+=sum[i]*(sum[i]-1)/2;
	}
	dfs(1,0);
//	//Debug begin
//	for(LL i=1; i<=n; i++) {
//		printf("%lld ",sum[i]);
//	}
//	//Debug end
	for(LL i=1; i<=m; i++) {
		ans+=sum[lsc[i].u]+sum[lsc[i].v]-2*sum[lsc[i].hrq];
	}
	printf("%lld",ans);
	return 0;
}