某国家的网络传输系统可以看作是以首都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]);}
}