高等理論計算機科學 LCA+樹上差分（樹上的相交路徑條數）Hihocoder-1167

題目連結：Hihocoder-1167

主要思路：

多畫幾棵樹可以看出兩條路徑相交時隻有一條路徑的LCA落在另一條路徑上，故你可以求每個LCA落在幾條路徑上（若兩條路徑LCA相同，這時候就會算兩遍，故将LCA從路徑上剔除，特判即可）。

求每個LCA落在幾條路徑上就可以用樹上差分。

AC代碼：

#include<cstdio>
#include<algorithm>
#include<vector>
#define lowbit(x) x&-x
#define M 100005
using namespace std;
struct E {
	int to,nx;
} edge[M<<1];
int tot,head[M];
void Addedge(int a,int b) {
	edge[++tot].to=b;
	edge[tot].nx=head[a];
	head[a]=tot;
}
struct Path {
	int from,to;
	bool operator <(const Path &x)const {
		return to<x.to;
	}
} way[M];
struct p100 { //若兩條路徑相交則必有一條的LCA落在另一條上
	int n,m;
	int sz[M],fa[M],son[M],dep[M];
	void dfs(int now) {
		sz[now]=1;
		son[now]=0;
		for(int i=head[now]; i; i=edge[i].nx) {
			int nxt=edge[i].to;
			if(nxt==fa[now])continue;
			fa[nxt]=now;
			dep[nxt]=dep[now]+1;
			dfs(nxt);
			if(sz[son[now]]<sz[nxt])son[now]=nxt;
			sz[now]+=sz[nxt];
		}
	}
	int top[M];
	void redfs(int now) {
		if(son[now]) {
			int nxt=son[now];
			top[nxt]=top[now];
			redfs(nxt);
		}
		for(int i=head[now]; i; i=edge[i].nx) {
			int nxt=edge[i].to;
			if(nxt==fa[now]||nxt==son[now])continue;
			top[nxt]=nxt;
			redfs(nxt);
		}
	}
	int LCA(int a,int b) {//跳重鍊求LCA 
		while(top[a]!=top[b]) {
			if(dep[top[a]]<dep[top[b]])swap(a,b);
			a=fa[top[a]];
		}
		return dep[a]<dep[b]?a:b;
	}
	long long ans;
	void ansdfs(int now) {
		for(int i=head[now]; i; i=edge[i].nx) {
			int nxt=edge[i].to;
			if(nxt==fa[now])continue;
			ansdfs(nxt);
			sum[now]+=sum[nxt];//sum即為目前點在幾條線段上 
		}
		ans+=1ll*sum[now]*cnt[now]+1ll*cnt[now]*(cnt[now]-1ll)/2;//兩個LCA相同會多算出情況，故特判
	}
	int sum[M],cnt[M];
	void solve(int n,int m) {
		ans=0;
		this->n=n;
		this->m=m;
		dfs(1);
		top[1]=1;
		redfs(1);
		for(int i=1; i<=m; i++) {
			sum[way[i].from]++;//差分 
			sum[way[i].to]++;
			int x=LCA(way[i].from,way[i].to);
			sum[x]-=2;//不把LCA算上去 
			cnt[x]++;
		}
		ansdfs(1);
		printf("%lld\n",ans);
	}
} P100;
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<n; i++) {
		int a,b;
		scanf("%d%d",&a,&b);
		Addedge(a,b);
		Addedge(b,a);//***建反向邊 
	}
	for(int i=1; i<=m; i++) {
		scanf("%d%d",&way[i].from,&way[i].to);
		if(way[i].from>way[i].to)swap(way[i].from,way[i].to);
	}
	P100.solve(n,m);
}