2015陝西併査集

ある国のネットワーク伝送システムは首都Townを中心とした有向樹と見なすことができ、最初はTownに基地局が建てられただけで、他の都市の信号はすべてTownから伝送されてきたが、今では他の都市に基地局を設立し始め、都市の番号は1->nである.このうち都市1は首都であり、「Cx」は都市xに基地局を建設し、Qは問い合わせを代表する.
入力:各グループのデータは2つの正の整数nとm(1<=n,m<=100000)を含み、それぞれ都市とコマンド数を表し、次のn-1行、各行に2つの整数uとvがあり、uからvへのネットワーク伝送路を表し、その後m行コマンド
≪出力｜Output｜oem_src≫:クエリーごとに1つの数を出力します.
例:3 4
       1    2
       2    3
       Q    3
       C    2
       Q    2
       Q    3
最適化されていない並列調査セットであることは明らかであるが,最適化されていないと必ずタイムアウト==である.
毎回建ててその点の父を彼自身に設定して、しかしこのように毎回検索してすべて一回探して、もし圧縮の経路はまたその効果に達しないならば
いずれにしても当時はできなかったし、今どこに提出するか見つからないので、他人の考えを大体見た.
配列でコマンドを記録し、まず「Cx」点の上位レベルを自分に設定し、コマンドを逆方向に開始し、質問であれば出力を検索する.基地局を構築する場合は、このポイントの上位レベルを最初に入力したときの上位レベルに変更し、まっすぐ行ってクエリー結果を保存して出力します.

while(scanf("%d%d",&n,&m)!= EOF)
{
   for(int 1;i < n;i++)
   {
       int u,v;
       scanf("%d%d",&u,&v);
       p[v] = u;
    }
    for(int i = 2;i <= n;i++)
        f[i] = p[i];
    f[1] = 1;
    for(int i = 0;i < m;i++)
    {
       scanf("%s%d",cmd,&x[i]);
       opr[i] = cmd[0];
       if(opr[i] == 'C')
       {
         f[x[i]] = x[i];
        }
    }
    for(int i = m - 1;i >= 0;i --)
    {
       if(opr[i] == 'C')
         f[x[i]] = p[x[i]];
       else
         ans[i] = find[x[i]];
    }
    for(int i = 0;i < m;i++)
    {
      if(opr[i] == 'Q')
      printf("%d
",ans[i]);
    }
}