Source Code
Problem: 1330		User: fyq
Memory: 9292K		Time: 94MS
Language: G++		Result: Accepted

    * Source Code

      #include <cstdio>
      #include <cstring>
      #include <cmath>
      #define maxn 100001

      using namespace std;

      typedef struct node
      {
          int x,y,next;
      }node;

      int e[maxn+1],t[maxn+1],h[maxn+!1];
      int f[maxn+1][20];
      bool mark[maxn+1];
      int first[maxn+1];
      node g[maxn+1];
      int fa[maxn+1];
      int n,total,root,counter;
      int ta,tb;

      void add(int x,int y)
      {
          g[++total].x = x; g[total].y = y;
          g[total].next = first[x]; first[x] = total;
      }

      void init()
      {
          scanf("%d",&n);
          total = 0;
          for (int i=1;i<=n;i++)
              {
                  first[i] = -1;
                  fa[i] = i;
              }
          int deg[maxn+1]={};
          int a,b;
          for (int i=1;i<=n-1;i++)
              {
                  scanf("%d%d",&a,&b);
                  add(a,b);
                  fa[b] = a;
                  deg[b] ++;
              }
          /*for (int i=1;i<=n;i++)
              printf("%d %d\n",i,fa[i]);*/
          scanf("%d%d",&ta,&tb);
          for (int i=1;i<=n;i++)
              if (!deg[i])
                  root = i;
          memset(mark,0,sizeof(mark));
      }

      void dfs(int x,int depth)
      {
          //printf("%dt\n",x);
          e[++counter] = x;
          t[x] = counter;
          h[counter] = depth;
          for (int temp=first[x];temp!=-1;temp = g[temp].next)
              {
                  dfs(g[temp].y,depth+1);
                  e[++counter] = x;
                  h[counter] = depth;
              }
      }

      void rmq_prepare(int *a)
      {
          memset(f,0,sizeof(f));
          for (int i=1;i<=counter;i++)
              f[i][0] = i;
          //printf("counter:%d log(counter):%f\n",counter,log(counter));
          int maxj = log(counter)/log(2);
          for (int j=1;j<=maxj;j++)
              for (int i=1;i<=counter-j+1;i++)
                  {
                      if (a[f[i][j-1]]<a[f[i + (1<<(j - 1))][j-1]])
                          f[i][j] = f[i][j-1];
                      else
                          f[i][j] = f[i + (1<<(j - 1))][j-1];
                  }
      }

      int rmq(int *a,int i,int j)
      {
          int k = log(j - i + 1)/log(2);
          if (a[f[i][k]]<a[f[j - (1<<k) + 1][k]])
              return f[i][k];
          return f[j - (1<<k) + 1][k];
      }

      bool find(int x,int y)
      {
          int k = x;
          while (fa[k]!=k)
              {
                  //printf("%d %d %d\n",x,y,k);
                  if (k==y) return 1;
                  k = fa[k];
              }
          return 0;
      }

      int main()
      {
          int test_case;
          scanf("%d",&test_case);
          for (int i=1;i<=test_case;i++)
              {
                  init();
                  counter = 0;/*
                  if (find(ta,tb))
                      {
                          printf("%d\n",ta);
                          continue;
                      }
                  if (find(tb,ta))
                      {
                          printf("%d\n",tb);
                          continue;
                      }*/
                  dfs(root,1);
                  if (t[ta]>t[tb]) {int temp = ta; ta = tb; tb = temp;}
                  /*printf("%d %d\n",e[t[ta]],ta);
                  printf("%d %dt\n",t[ta],t[tb]);
                  for (int i=t[ta];i<=t[tb];i++)
                      {
                          printf("%d %d %d\n",i,e[i],h[i]);
                      }*/
                  rmq_prepare(h);
                  //printf("f`%d\n",f[14][3]);
                  //printf("%d\n",rmq(h,t[ta],t[tb]));
                  printf("%d\n",e[rmq(h,t[ta],t[tb])]);
              }
          return 0;
      }

• 貌似转成RMQ数据量小了有点慢。。。我79ms。。。 不知道用±1RMQ的O（n）方法会怎么样。。。 (2124) Debugcool 2010-08-05 09:41:50