1.改造二叉樹

【題目描述】

小Y在學樹論時看到了有關二叉樹的介紹：在計算機科學中，二叉樹是每個結點最多有兩個子結點的有序樹。通常子結點被稱作“左孩子”和“右孩子”。二叉樹被用作二叉搜索樹和二叉堆。隨后他又和他人討論起了二叉搜索樹。

什么是二叉搜索樹呢？二叉搜索樹首先是一棵二叉樹。設key[p]表示結點p上的數值。對于其中的每個結點p，若其存在左孩子lch，則key[p]>key[lch]；若其存在右孩子rch，則key[p]<key[rch]；注意，本題中的二叉搜索樹應滿足對于所有結點，其左子樹中的key小于當前結點的key，其右子樹中的key大于當前結點的key。

小Y與他人討論的內容則是，現在給定一棵二叉樹，可以任意修改結點的數值。修改一個結點的數值算作一次修改，且這個結點不能再被修改。若要將其變成一棵二叉搜索樹，且任意時刻結點的數值必須是整數（可以是負整數或0），所要的最少修改次數。

相信這一定難不倒你！請幫助小Y解決這個問題吧。

?

【輸入格式】

第一行一個正整數n表示二叉樹結點數。結點從1~n進行編號。

第二行n個正整數用空格分隔開，第i個數ai表示結點i的原始數值。

此后n - 1行每行兩個非負整數fa, ch，第i + 2行描述結點i + 1的父親編號fa，以及父子關系ch，(ch = 0 表示i + 1為左兒子，ch = 1表示i + 1為右兒子)。

結點1一定是二叉樹的根。

?

【輸出格式】

僅一行包含一個整數，表示最少的修改次數。

?

【樣例輸入】

3

2 2 2

1 0

1 1

?

【樣例輸出】

2

?

【數據范圍】

20 % ：n <= 10 , ai <= 100.

40 % ：n <= 100 , ai <= 200

60 % ：n <= 2000 .

100 % ：n <= 10 ^ 5 , ?ai < 2 ^ 31.?

?

對樹的知識了解的人可能一下就可以反應過來，我們針對一個小的分支看，是左邊<父節點<右邊。。。。然后這個順序想到了啥

對，就是中序遍歷，中序遍歷：左中右。。。。然后題中也說到，整個左子樹要小于父節點

然后我們就能夠推出來，改造二叉樹的中序遍歷是嚴格上升的

然后題就轉換成了求中序遍歷，然后求最長嚴格上升子序列。。。。

求最長嚴格上升子序列可以進行優化，因為是嚴格上升，所以第i個至少比第i-1個大1，然后我們可以對這個序列里的數減去他的序數，就是求最長不下降子序列

?

這題還有一個需要注意的地方是，數據范圍太大，不適合普通的LIS做法，要進行優化。。。

優化方式是開個數組f[i]記錄滿足條件的第i個數最小是f[i]

我們畫圖理解

然后我們唯一要處理就是圖中第一個6和4 對f的影響

這里我們可以用二分的方式，因為是上升子序列，所以我們只需要二分找到第一個比當前小的數，然后用當前數取代之前那個數

圖中就是，當i=4時，二分找到第一個比他小的i=1,a[i]=1的數，然后發現a[2]<a[4]就用2取代這個位置的6,f[2]=6，9的取代同理

這樣做就大大優化了時間，不會超時

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<cstdlib> 7 #include<queue> 8 #define maxn 100005 9 using namespace std; 10 11 struct node{ 12 int l,r,val; 13 }tree[maxn]; 14 15 int n,a[maxn],f[maxn],ans,tot; 16 17 void dfs(int pos){//中序遍歷左中右 18 if(pos<1)return; 19 dfs(tree[pos].l); 20 tot++; 21 a[tot]=tree[pos].val-tot;//求最長不下降子序列 22 dfs(tree[pos].r); 23 } 24 25 int find(int l,int r,int x) 26 { 27 while(l<=r){ 28 int mid=(l+r)/2; 29 if(f[mid]<=x)l=mid+1; 30 else r=mid-1; 31 } 32 return l; 33 } 34 35 int main() 36 { 37 freopen("binary.in","r",stdin); 38 freopen("binary.out","w",stdout); 39 scanf("%d",&n); 40 for(int i=1;i<=n;i++){ 41 scanf("%d",&tree[i].val); 42 }int fa,so; 43 for(int i=2;i<=n;i++){ 44 scanf("%d%d",&fa,&so); 45 if(so==0)tree[fa].l=i; 46 else tree[fa].r=i; 47 } 48 dfs(1); 49 f[1]=a[1];ans=1; 50 for (int i=2;i<=n;i++)//最長不降字串一類的信方式 51 { 52 if (a[i]>=f[ans]) 53 f[++ans]=a[i]; 54 else 55 f[find(1,ans,a[i])]=a[i];//當合法字串長度一樣，盡量用小的那一個 56 } 57 printf("%d\n",n-ans); 58 /* 59 6 60 4 6 5 1 9 6 61 1 0 62 1 1 63 2 0 64 2 1 65 3 1 66 */ 67 } View Code

總結：在遇到和樹相關的題時，如果允許，可以從前中后遍歷去查詢問題。。。

　　　最長上升或不降這一類的題，可以進行優化，優化方式如文。。。

　　　還有一點就是可以合理運用容斥原理，我們這是求最少不合法的個數，然后可以轉換成總數減去合法的最大個數

?

轉載于:https://www.cnblogs.com/Danzel-Aria233/p/7646763.html

總結

以上是生活随笔為你收集整理的[noip模拟]改造二叉树LIS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。