2015陕西 并查集

某国家的网络传输系统可以看作是以首都Town为中心的有向树，一开始只是Town建有基站，所有其他城市的信号全是从Town传输过来的，现在他们开始在其他城市建立基站，城市的编号为1->n；其中城市1为首都，"C x"代表在城市x处建立基站，Q代表询问。

输入：每组数据包含2个正整数n和m（1<= n,m <= 100000）,分别表示城市和命令数，接下来n-1行，每行有两个整数u和v，代表一条由u到v的网络传输通道，之后m行命令

输出：对于每个查询输出一个数

样例: 3    4

    1    2

    2    3

    Q    3

    C    2

    Q    2

    Q    3

可以明显看出是一个没优化的并查集，但是不优化必定超时= =。

每一次建就把那个点的父亲设定为他自己，但是这样每一次查询都要查找一次，如果压缩路径又达不到那个效果了

反正当时没做出来，而且现在找不到在哪提交，就大概看了下别人的思路

用数组记录下命令，先把"C x"点的上一级设定为自己，命令反向开始，如果是询问，则查找输出；如果是建基站，则把这个点的上一级改为最开始输入时他的上一级，然后一直下去，把查询结果保存再输出。

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]];elseans[i] = find[x[i]];}for(int i = 0;i < m;i++){if(opr[i] == 'Q')printf("%d\n",ans[i]);}
}