2015北京网络赛 Couple Trees 倍增算法

2015北京网络赛 Couple Trees

题意：两棵树，求不同树上两个节点的最近公共祖先

思路：比赛时看过的队伍不是很多，没有仔细想。今天补题才发现有个倍增算法，自己竟然不知道。

　　解法来自 qscqesze ，这个其实之前如果了解过倍增的话还是不是很难，不过这题的数据也不是很给力，极限数据理论上是过不了的。

　　其他解法有树链剖分？并不是很清楚。就这样水过了吧。。。

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <algorithm>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <string>

 #include <cstring>

 #include <map>

 #include <stack>

 #include <set>

 #define LL long long

 #define eps 1e-8

 #define INF 0x3f3f3f3f

 #define MAXN 100005

 using namespace std;

 int f1[MAXN][], f2[MAXN][];

 int deep1[MAXN], deep2[MAXN];

 int step1, step2, ans;

 void work(int x, int y){

     step1 = step2 = ;

     while (x != y){

         if (x < y){

             //x < y means y is not x's ancestor, so let y up

             for (int i = ; i >= ; i--){

                 if (f2[y][i] > x){

                     y = f2[y][i];

                     step2 +=  << i;

                     break;

                 }

             }

             y = f2[y][];

             step2++;

         }

         else{

             for (int i = ; i >= ; i--){

                 if (f1[x][i] > y){

                     x = f1[x][i];

                     step1 +=  << i;

                     break;

                 }

             }

             x = f1[x][];

             step1++;

         }

     }

     ans = x;

 }

 int main()

 {

 #ifndef ONLINE_JUDGE

     freopen("in.txt", "r", stdin);

     //freopen("out.txt", "w", stdout);

 #endif // OPEN_FILE

     int n, m;

     while (~scanf("%d%d", &n, &m)){

         int x, y;

         deep1[] = deep2[] = ;

         for (int i = ; i <= ; i++){

             f1[][i] = f2[][i] = ;

         }

         for (int i = ; i <= n; i++){

             scanf("%d", &x);

             f1[i][] = x;

             deep1[i] = deep1[x] + ;

             for (int j = ; j <= ; j++){

                 f1[i][j] = f1[f1[i][j - ]][j - ];

             }

         }

         for (int i = ; i <= n; i++){

             scanf("%d", &x);

             f2[i][] = x;

             deep2[i] = deep2[x] + ;

             for (int j = ; j <= ; j++){

                 f2[i][j] = f2[f2[i][j - ]][j - ];

             }

         }

         ans = ;

         for (int i = ; i <= m; i++){

             scanf("%d%d", &x, &y);

             x = (x + ans) % n + ;

             y = (y + ans) % n + ;

             work(x, y);

             printf("%d %d %d\n", ans, step1, step2);

         }

     }

 }

巴特西

2015北京网络赛 Couple Trees 倍增算法

最新文章

热门文章