#Description

給你一顆有 n 個(gè)點(diǎn)的樹，其中 1 號(hào)點(diǎn)為根節(jié)點(diǎn)，每個(gè)點(diǎn)都有一個(gè)權(quán)值 vali
你可以從樹中選擇一些點(diǎn)，注意如果 i 與 j 都被選中且 j 在 i 的子樹內(nèi)，那么必須滿足 vali >valj
請你求出最多能同時(shí)選出多少個(gè)點(diǎn)

#Input

第一行一個(gè)正整數(shù) n
下接 n 行，每行兩個(gè)正整數(shù) vali ,fi ，其中 vali 表示該點(diǎn)權(quán)值，fi 表示這個(gè)結(jié)點(diǎn)的父親結(jié)點(diǎn)
f1 = 0;?2 ≤ i ≤ n,fi < i

#Output

一行一個(gè)整數(shù)，表示答案

#Sample Input

6
3 0
1 1
2 1
3 1
4 1
5 1

#Sample Output

5

#Data Constraint

對于 30% 的數(shù)據(jù)滿足 n ≤ 2000
對于另 20% 的數(shù)據(jù)滿足 fi = i ? 1
對于 100% 的數(shù)據(jù)滿足 n ≤ 100000,f1 = 0,?2 ≤ i ≤ n,fi < i,vali ≤ 10^9

#Solution

• 先考慮一條鏈的情況，那顯然是相當(dāng)于求一個(gè)序列的 LIS ！

• 仍然是對每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)單調(diào)上升序列的 $multiset$ 。

• 在轉(zhuǎn)移到一般樹上的情況，可以發(fā)現(xiàn)各個(gè)子樹是互不干擾的。

• 像求普通LIS一樣，我們將每個(gè)子樹的 $multiset$ 都合并到父親上。

• 注意要用啟發(fā)式合并，即小的合并到大的上，這樣可以節(jié)省很多時(shí)間。

• 一個(gè)子樹的信息被合并后就不再需要了，于是我們可以清空它，這樣可以節(jié)省很多空間。

• 之后我們將 $val[x]$ 在 $multiset$ 上二分并替換即可（怎么就是普通 LIS 啊？！）。

• 時(shí)間復(fù)雜度 $O(NlogN)$ 。

#Code

#include<cstdio> #include<algorithm> #include<cctype> #include<set> using namespace std; const int N=1e5+5; int tot; int first[N],next[N],en[N]; int val[N]; multiset<int>f[N]; multiset<int>::iterator it; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y; } void dfs(int x) {for(int i=first[x];i;i=next[i]){int y=en[i];dfs(y);if(f[x].size()<f[y].size()) swap(f[x],f[y]);for(it=f[y].begin();it!=f[y].end();it++) f[x].insert(*it);f[y].clear();}it=f[x].lower_bound(val[x]);if(it!=f[x].end()) f[x].erase(it);f[x].insert(val[x]); } int main() {int n=read();for(int i=1,fa;i<=n;i++){val[i]=read();if(fa=read()) insert(fa,i);}dfs(1);printf("%d",f[1].size());return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5609. 【NOI2018模拟3.28】Tree BZOJ 4919: [Lydsy1706月赛]大根堆的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。