2540428_tle.cpp

来自「做的POJ的一些题目」· C++ 代码 · 共 73 行

#include<iostream>
using namespace std;
struct
{
       int sum;
       int counts;
       int com[200]; //以空间换时间 
       int father;
       int lev;
}node[30001];
void init()
{
     for(int i=1;i<=30000;i++)
     {     
          node[i].counts=0;
          node[i].sum=1;
          node[i].father=i;
     }
}
void mov(int a,int b)//b for a child
{
     while(b!=node[b].father)
       b=node[b].father;
     node[a].counts++;
     node[a].com[node[a].counts]=b;
     node[b].father=a;
     node[b].lev=node[a].counts;
     while(a!=node[a].father)
     {
         node[a].sum=node[a].sum+node[b].sum;
         a=node[a].father;
     }
     node[a].sum=node[a].sum+node[b].sum;
}
int find(int x)
{
     int c=node[x].sum;
     while(node[x].father!=x)
     {
          int lev=node[x].lev;
          x=node[x].father;
          for(int i=lev+1;i<=node[x].counts;i++)
              c=node[node[x].com[i]].sum+c;
     }
     return c;
}
int main()
{
    int p;
    cin>>p;
    init();
    for(int i=1;i<=p;i++)
    {
         char c;
         cin>>c;
         if(c=='M')
         {
             int x,y;
             cin>>x;
             cin>>y;
             mov(x,y);          
         } 
         else if(c=='C')
         {
              int x;
              cin>>x;
              cout<<find(x)-1<<endl;     
         }       
    }
    system("pause");
    return 0;
}