当前位置：首页 > news >正文

poj 1470（简单LCA 倍增法）

news 来源：原创 2024/5/3 1:40:28

题意：给你一个树，有若干个询问，然后让你统计每个结点在询问中做了几次LCA。按照结点顺序输出。

思路：这也是简单的LCA题目，我用的是倍增法。每次查询在相应结点标记上++，最后输出即可。这道题的输入处理比较烦，而且第一个输入的结点并不是根节点。这要注意一下

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <queue>
 8 #include <stack>
 9 #include <vector>
10 #include <set>
11 #include <map>
12 #define MP(a, b) make_pair(a, b)
13 #define PB(a) push_back(a)
14 
15 using namespace std;
16 
17 typedef long long ll;
18 typedef pair<int ,int> pii;
19 typedef pair<unsigned int, unsigned int> puu;
20 typedef pair<int ,double> pid;
21 typedef pair<ll, int> pli;
22 
23 const int INF = 0x3f3f3f3f;
24 const double eps = 1e-6;
25 const int LEN = 1000+10;
26 const int LOG_LEN = 100;
27 vector<int> Map[LEN];
28 int root, parent[LOG_LEN][LEN], depth[LEN], ind[LEN];
29 
30 void dfs(int v, int p, int d){
31     parent[0][v] = p;
32     depth[v] = d;
33     for(int i=0; i<Map[v].size(); i++){
34         if(Map[v][i] != p) dfs(Map[v][i], v, d+1);
35     }
36 }
37 
38 void init(int n){
39     dfs(root, -1, 0);
40     for(int k=0; k+1<LOG_LEN; k++){
41         for(int v=1; v<=n; v++){
42             if(parent[k][v] < 0) parent[k+1][v] = -1;
43             else parent[k+1][v] = parent[k][parent[k][v]];
44         }
45     }
46 }
47 
48 int lca(int u, int v){
49     if(depth[u] > depth[v])swap(u,v);
50     for(int k=0; k < LOG_LEN; k++){
51         if((depth[u] - depth[v]) >> k & 1) v = parent[k][v];
52     }
53     if(u==v) return u;
54     for(int k=LOG_LEN-1; k>=0; k--){
55         if(parent[k][v] != parent[k][u]){
56             u = parent[k][u];
57             v = parent[k][v];
58         }
59     }
60     return parent[0][u];
61 }
62 
63 int main()
64 {
65 //    freopen("in.txt", "r", stdin);
66 
67     int n, a, b, tn, q;
68     while(scanf("%d", &n)!=EOF){
69         for(int i=0; i<LEN; i++)Map[i].clear();
70         memset(ind, 0, sizeof ind);
71         for(int i=1; i<=n; i++){
72             scanf("%d:(%d)", &a, &tn);
73             for(int j=0; j<tn; j++){
74                 scanf("%d", &b);
75                 Map[a].PB(b);
76                 Map[b].PB(a);
77                 ind[b]++;
78             }
79         }
80         for(int i=1; i<=n; i++)if(!ind[i]){root = i;break;}
81         memset(ind, 0, sizeof ind);
82         init(n);
83         scanf("%d", &q);
84         for(int i=0; i<q; i++){
85             while(getchar() != '(');
86             scanf("%d%d", &a, &b);
87             while(getchar() != ')');
88             ind[lca(a, b)] ++;
89         }
90         for(int i=1; i<=n; i++){
91             if(!ind[i])continue;
92             printf("%d:%d\n", i, ind[i]);
93         }
94     }
95     return 0;
96 }