HDU 1856 More is betterおよびルックアップパス圧縮

しばらくやって調べました.個人的には、問題の解き方を利用して調べるのは単調だと思います.
1、各ノードの親ノードを記録する配列を開き、初期化する
2、一対の関連データを与え、検索する
3.検索結果に基づいてルートが同じ集合に属していない場合はマージ
もちろん、最適化もできます.主に、遡及時に各ノードの親ノードがツリーのルートノードになるように再帰を検索します.今度探せばいい
検索の長さを下げます.次に,1つの配列を用いて各木の高さを記録することができる.結合時に低い木を高い木にリンクし、新しく生成された木が尽きるようにします.
量が少ない.
この2つのリンクを見ることができます:クリックしてリンクを開くとクリックしてリンクを開く
 
私がこの問題をする考えは:
1、2本の木をマージする場合、ルートノードが異なる場合にマージするのが一般的です.実は、この要求も実際の状況から見ることができると思います.
単純な併合問題なら同じでも併合でき、併合前後に変化はない.しかし、例えば本題は異なるものでなければ統合されません.
同じマージもnum[]に影響します.
2、注記されたコードは、マージ時に低い木を高い木にリンクするために使用されます.しかし、スペースが足りません.
コードを見ると、aをルートとするツリーがbをルートとするツリーにリンクされた後、height[a]は0に割り当てるべきだという問題があるかもしれません.コード
そうはしていません.処理しなくても影響しないからです.どうしてですか.aはもう根ではないからだ.次に関連するエッジのセット(a,c)を処理する場合でも、
aのルートとcでリンクします.つまりaは二度と根にならず、height[a]も二度と使われない.
 
ACコード:

#include
using namespace std;

const int MAX=10000001;
int father[MAX];  //father[i]  i    
int num[MAX];    //num[i] i      
//int height[MAX];  //    

void initial()   //   
{
	for(int i=0;iheight[tmpa])  //             
		{
			father[tmpa]=tmpb;
			num[tmpb]+=num[tmpa];
			num[tmpa]=0;
		}
		else
		{
			father[tmpb]=tmpa;
			num[tmpa]+=num[tmpb];
			num[tmpb]=0;

			if(height[tmpa]==height[tmpb])
				height[tmpa]++;
		}
		*/
	}
}

int maxNode()   //         
{
	int tmp=0;
	for(int i=0;itmp)
			tmp=num[i];
	}

	return tmp;
}

void preDeal(int n)   //   
{
	int a,b;

    for(int i=0;i