牛客网-“景驰科技杯”2018年华南理工大学程序设计竞赛 B-一级棒 （树-路径压缩）

题目链接

题意：给出一个n，表示有n个节点0~n，0为根结点，随后给出n-1个数表示第i个节点连接的父节点

再给出一个q，随后q次操作：R u v 表示节点u~v之间的路径被访问的次数加1

Eg:5 0 1 1 3                          W x 表示请你输出经过x及他的父节点之间这条路被访问的情况

     5                                     若没有被访问过输出"Not yet",若被访问超过2次输出"Many times"

     R 2 4                               若只被访问过一次输出那次访问的路径端点（Eg：小端点 大端点）

     W 3 (输出:2 4）注意：要求输出访问过一次的情况时是输出路径端点（不一定是他和其父节点，试试左边样例）

     R 1 2

     W 2 (输出:Many times)

     W 1 (输出:Not yet)

解法：第一次访问路径u，v，直接对路径中的所有节点都进行访问+1的操作

      若访问到被访问过一次的路径时进行对其pre值进行修改为其父节点

    （目的：把被访问到第二次的路径都压缩起来，下次不在访问）

      若访问到被访问过两次的路径时直接根据其pre的并查集得到压缩路径后的终点（节省时间）

代码如下：

#include<cmath>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<stdio.h>  
#include<cmath>  
#include<iostream>  
using namespace std;
#define ll long long  
#define inf 0x3f3f3f3f  
const int maxn = 1e5 + 500;
struct node
{
	int l, r; //记录第一次访问时的路径端点  
	int dept; //记录该节点所在层数  
	int fa; //记录其父节点  
	int cnt; //对节点的访问次数进行统计（路径压缩后中间节点num最大2）  
}tre[maxn];
int pre[maxn];//并查集对树上操作超过2次的操作进行路径压缩处理  
int find(int x)
{
	if (pre[x] == x)
		return x;
	return pre[x] = find(pre[x]);
}
void operation(int x, int y)
{
	int u = x, v = y;//保留u，v（因为恰好是“一级棒的边”时，要回答恰好经过这条边的路径端点）  
	while (u != v)
	{
		if (tre[u].dept < tre[v].dept)swap(u, v); //先对深度大的进行向上前进操作（保证它们能相遇）  
		tre[u].cnt++;
		if (tre[u].cnt == 1)
			tre[u].l = min(x, y), tre[u].r = max(x, y);
		else
			pre[u] = tre[u].fa;
		u = find(tre[u].fa);
	}
}
int main()
{
	int n;
	while (~scanf("%d", &n))
	{
		for (int i = 1; i < n; i++)
		{
			scanf("%d", &tre[i].fa);
			tre[i].dept = tre[tre[i].fa].dept + 1;
			tre[i].cnt = 0;
			pre[i] = i;
		}
		int q, u, v;
		scanf("%d", &q);
		char s[2];
		while (q--)
		{
			scanf("%s", &s);
			if (s[0] == 'R')
			{
				scanf("%d%d", &u, &v);
				operation(u, v);
			}
			else
			{
				scanf("%d", &u);
				if (tre[u].cnt == 0) printf("Not yet\n");
				else if (tre[u].cnt == 1)printf("%d %d\n", tre[u].l, tre[u].r);
				else printf("Many times\n");
			}
		}
	}
	return 0;
}