hihoCoder #1167 : 高等理论计算机科学(LCA)

Description:

少女幽香这几天正在学习高等理论计算机科学，然而她什么也没有学会，非常痛苦。所以她出去晃了一晃，做起了一些没什么意义的事情来放松自己。
门前有一颗n个节点树，幽香发现这个树上有n个小精灵。然而这些小精灵都比较害羞，只会在一条特定的路径上活动。第i个小精灵会在ai到bi的路径上活动。
两个小精灵是朋友，当且仅当它们的路径是有公共点的。
于是幽香想要知道，有多少对小精灵a和b，a和b是朋友呢？其中a不等于b，a,b和b,a看做一对。

Input:

第一行n和P (1 <= n, P <=100000)，表示树的大小和小精灵的个数。树的节点从1到n标号。
接下来n-1行，每行两个数a,b，表示a到b之间有一条边。
接下来P行，第i行两个数ai,bi，表示小精灵i的活动范围是ai到bi，其中ai不等于bi。

Output:

一行答案，表示对数。

Sample Input:

6 3
1 2
2 3
2 4
4 5
4 6
1 3
1 5
5 6

Sample Output:

2

题目链接

对于小精灵的活动范围离线查询LCA，统计每个LCA节点i的LCA数量Cnt[i]，之后Dfs算出根节点到节点i的LCA数量值之和Sum[i]，计算每个小精灵活动范围路径上的其他小精灵活动范围LCA节点的个数（两端点a，b之间的个数就是Sum[a]+Sum[b]-2×Sum[LCA(a,b)]），最后由于某些节点不止是一条路径的LCA，需要对最终答案乘以C(2,Cnt)。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

struct Edge {
	int V, Next;
};

struct Query {
	int Q, Next;
	int Index;
};

struct Input {
	int U, V;
};

int N, P;
int Pre[maxn << 2];
Edge edges[maxn << 2];
int Head[maxn];
int Tot;
Query querys[maxn << 2];
int QHead[maxn];
int QTot;
int Vis[maxn];
int Ancestor[maxn];
int Answer[maxn];
int Sum[maxn];
int Cnt[maxn];
Input inputs[maxn];
long long Ans;

int Find(int X) {
	int R = X;
	while (Pre[R] != -1) {
		R = Pre[R];
	}
	return R;
}

void Join(int U, int V) {
	int RU = Find(U), RV = Find(V);
	if (RU != RV) {
		Pre[RU] = RV;
	}
}

void Init() {
	Tot = 0;
	memset(Head, -1, sizeof(Head));
	QTot = 0;
	memset(QHead, -1, sizeof(QHead));
	memset(Vis, false, sizeof(Vis));
	memset(Pre, -1, sizeof(Pre));
	memset(Ancestor, 0, sizeof(Ancestor));
	memset(Sum, 0, sizeof(Sum));
	memset(Cnt, 0, sizeof(Cnt));
}

void Addedge(int U, int V) {
	edges[Tot] = Edge {V, Head[U]};
	Head[U] = Tot++;
}

void AddQuery(int U, int V, int Index) {
	querys[QTot] = Query {V, QHead[U], Index};
	QHead[U] = QTot++;
	querys[QTot] = Query {U, QHead[V], Index};
	QHead[V] = QTot++;
}

void Tarjan(int Node) {
	Ancestor[Node] = Node;
	Vis[Node] = true;
	for (int i = Head[Node]; ~i; i = edges[i].Next) {
		if (Vis[edges[i].V]) {
			continue;
		}
		Tarjan(edges[i].V);
		Join(Node, edges[i].V);
		Ancestor[Find(Node)] = Node;
	}
	for (int i = QHead[Node]; ~i; i = querys[i].Next) {
		if (Vis[querys[i].Q]) {
			Answer[querys[i].Index] = Ancestor[Find(querys[i].Q)];
		}
	}
}

void Dfs(int Cur, int Parent) {
	Vis[Cur] = true;
	Sum[Cur] = Sum[Parent] + Cnt[Cur];
	for (int i = Head[Cur]; ~i; i = edges[i].Next) {
		if (Vis[edges[i].V]) {
			continue;
		}
		Dfs(edges[i].V, Cur);
	}
}

int main(int argc, char *argv[]) {
	Init();
	scanf("%d%d", &N, &P);
	for (int i = 1, U, V; i < N; ++i) {
		scanf("%d%d", &U, &V);
		Addedge(U, V);
	}
	for (int i = 1; i <= P; ++i) {
		scanf("%d%d", &inputs[i].U, &inputs[i].V);
		AddQuery(inputs[i].U, inputs[i].V, i);
	}
	Tarjan(1);
	for (int i = 1; i <= P; ++i) {
		Cnt[Answer[i]]++;
	}
	memset(Vis, false, sizeof(Vis));
	Dfs(1, 0);
	Ans = 0;
	for (int i = 1; i <= P; ++i) {
		Ans += Sum[inputs[i].U] + Sum[inputs[i].V] - 2 * Sum[Answer[i]];
	}
	for (int i = 1; i <= N; ++i) {
		Ans += 1LL * Cnt[i] * (Cnt[i] - 1) / 2;
	}
	printf("%lld\n", Ans);
    return 0;
}