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;
}
