牛客網-“景馳科技杯”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;
}