hihoCoder挑战赛11.题目4 : 高等理论计算机科学(LCA)

clj在某场hihoCoder比赛中的一道题，表示clj的数学题实在6，这道图论貌似还算可以。。。

题目链接：http://hihocoder.com/problemset/problem/1167

由于是中文题目，题意不再赘述。

对于任意两条小精灵的活动路径a和b，二者相交的判断条件为b的两个端点的LCA在a的路径上；那么我们可以首先将每个活动路径端点的LCA离线预处理出来，对每个节点LCA值+1。

然后以某个节点(我选择的是节点1)为根进行深搜，算出一条从节点1到节点x的LCA值和，那么任意路径a(假设其两端点分别是A和B)上的节点个数就是sum[A] + sum[B] - 2 * sum[LCA(A,B)]。

最后，对于某些点，如果它是不止一条路径的LCA，那么我们只需要对最终答案乘以C(LCAnum, 2)的组合数就好。

【PS：clj给出的题解中，采用了点分治+LCA的方式，虽然看懂了题意，但是表示对递归分治之后的路径，如何求出其上的LCAnum，并没有多好的想法，还望巨巨能指点一下，Thx~】

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long LL;
 6 #define MAXN 100010
 7 struct Edge {
 8     int to, next;
 9 } edge[MAXN << 1];
10 struct Node {
11     int to, next, num;
12 } Query[MAXN << 1];
13 struct node {
14     int u, v, lca;
15 } input[MAXN];
16 int totEdge, totQuery, n, m;
17 int headEdge[MAXN], headQuery[MAXN];
18 int ancestor[MAXN], father[MAXN], LCAnum[MAXN], sum[MAXN];
19 bool vis[MAXN];
20 void addEdge(int from, int to) {
21     edge[totEdge].to = to;
22     edge[totEdge].next = headEdge[from];
23     headEdge[from] = totEdge++;
24 }
25 void addQuery(int from, int to, int x) {
26     Query[totQuery].to = to;
27     Query[totQuery].num = x;
28     Query[totQuery].next = headQuery[from];
29     headQuery[from] = totQuery++;
30 }
31 void init() {
32     memset(headEdge, -1, sizeof(headEdge));
33     memset(headQuery, -1, sizeof(headQuery));
34     memset(father, -1, sizeof(father));
35     memset(vis, false, sizeof(vis));
36     memset(sum, 0, sizeof(sum));
37     memset(LCAnum, 0, sizeof(LCAnum));
38     totEdge = totQuery = 0;
39 }
40 int find_set(int x) {
41     if(x == father[x]) return x;
42     else return father[x] = find_set(father[x]);
43 }
44 void union_set(int x, int y) {
45     x = find_set(x); y = find_set(y);
46     if(x != y) father[y] = x;
47 }
48 void Tarjan(int u) {
49     father[u] = u;
50     for(int i = headEdge[u]; i != -1; i = edge[i].next) {
51         int v = edge[i].to;
52         if(father[v] != -1) continue;
53         Tarjan(v);
54         union_set(u, v);
55     }
56     for(int i = headQuery[u]; i != -1; i = Query[i].next) {
57         int v = Query[i].to;
58         if(father[v] == -1) continue;
59         input[Query[i].num].lca = find_set(v);
60     }
61 }
62 void DFS(int u, int pre) {
63     vis[u] = 1;
64     sum[u] = sum[pre] + LCAnum[u];
65     for(int i = headEdge[u]; i != -1; i = edge[i].next) {
66         int v = edge[i].to;
67         if(vis[v]) continue;
68         DFS(v, u);
69     }
70 }
71 int main() {
72     init();
73     scanf("%d%d", &n, &m);
74     for(int i = 0; i < n - 1; i++) {
75         int a, b;
76         scanf("%d%d", &a, &b);
77         addEdge(a, b); addEdge(b, a);
78     }
79     for(int i = 0; i < m; i++) {
80         int a, b;
81         scanf("%d%d", &a, &b);
82         input[i].u = a, input[i].v = b;
83         addQuery(a, b, i); addQuery(b, a, i);
84     }
85     Tarjan(1);
86     for(int i = 0; i < m; i++)
87         LCAnum[input[i].lca]++;
88     DFS(1, 0);
89     LL ans = 0;
90     for(int i = 0; i < m; i++) {
91         ans += (sum[input[i].u] + sum[input[i].v] - 2 * sum[input[i].lca]);
92     }
93     for(int i = 1; i <= n; i++) {
94         ans += (LL)LCAnum[i] * (LCAnum[i] - 1) / 2;
95     }
96     printf("%lld
", ans);
97     return 0;
98 }

View Code

转载：）