HDU 3974 태 스 크 할당 및 집합 찾기 + 비 경로 압축

제목 링크: 제목 전송 문 제목 대의: 현재 나무 한 그루, 다음 과 같은 조작 이 있 습 니 다.
4. 567917. 노드 x 와 그의 모든 자손 의 색깔 은 k 로 변경 된다
4. 567917. 노드 x 의 색상 에 대답 해 달라 고 요구 합 니 다.처음에는 모든 점 이 염색 되 지 않 았 다.Input 첫 줄 의 정수 T (T < = 10) 는 샘플 그룹 수 를 나타 낸다.모든 테스트 사례: 첫 번 째 줄 의 정수 n (n < = 5e4) 은 나무의 노드 개 수 를 나타 낸다.다음 n 줄, 줄 마다 두 개의 정수 u, v (1 < = u, v < = n) 는 나무 에 있 는 u 의 부모 노드 가 v 임 을 나타 낸다.다음 줄 의 정수 q (q < = 5e4) 는 문의 수 를 표시 합 니 다.다음 q 줄: 염색 작업 을 하려 면 "T x k" 를 입력 하고, 검색 작업 을 위해 서 는 "C x" 를 입력 하 십시오. (1 < = x < = n, 0 < = y < = 1e9)Output 각 테스트 샘플 은 먼저 "Case \ # x:" 줄 을 출력 합 니 다. 그 중에서 x 는 현재 샘플 번호 입 니 다.모든 문의 작업 에 대해 하나의 정 수 를 출력 하고 현재 노드 의 색 을 표시 하 며 염색 되 지 않 으 면 출력 - 1.Sample Input

1 
5 
4 3 
3 2 
1 3 
5 2 
5 
C 3 
T 2 1
 C 3 
T 3 2 
C 3

Sample Output

Case #1:
-1 
1 
2

사고: 딱 봐 도 나무 구조 이 고 dfs 순서 가 아니면 집합 을 찾 습 니 다. dfs 는 라인 트 리 와 시간 스탬프 와 결합 해 야 하기 때문에 집합 을 찾 는 것 이 간단 합 니 다. 그러나 여 기 는 도로 힘 으로 압축 할 수 없습니다. (저 는 여기 잘못 되 었 습 니 다) * * * 경로 압축 으로 찾 을 때 뿌리 노드 는 부자 노드 가 아니 기 때 문 입 니 다. * 코드 를 볼 수 있 습 니 다.코드:

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long int ll;
const ll N = 5e4 + 100;
ll color[N],f[N],time[N];
int main()
{
 ios::sync_with_stdio(false);
 int t,n;
 cin>>t;
 int flag=0;
 while(t--)
 {
  flag++;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
   f[i]=i;
   color[i]=-1;
   time[i]=-1;
  }
  for(int i=1;i<n;i++)
  {
   int x,y;
   cin>>x>>y;
   f[x]=y;//       
  }
  int q,cnt=0;
  cin>>q;
  cout<<"Case #"<<flag<<":"<<'
';
  while(q--)
  {
   char p;
   int x,y;
   cin>>p;
   if(p=='C')
   {
    cin>>x;
    int cnr=x,ans=color[cnr],lastt=-1;
    while(cnr!=f[cnr])
    {
     if(time[cnr]>lastt)//            ，       
     {
      lastt=time[cnr]; 
      ans=color[cnr];
     }
     cnr=f[cnr];//    ，     
    }
    if(time[cnr]>lastt)
    {
     lastt=time[cnr];
     ans=color[cnr];
    }//     ，                  
    cout<<ans<<'
';
    
   }
   else if(p=='T')
   {
    cin>>x>>y;
    color[x]=y;
    time[x]=cnt++;
   }
  }
 }
 return 0; 
}