Description
給定一棵n個節點的有根樹，編號依次為1到n，其中1號點為根節點。每個點有一個權值v_i。
你需要將這棵樹轉化成一個大根堆。確切地說，你需要選擇盡可能多的節點，滿足大根堆的性質：對于任意兩個點i,j，如果i在樹上是j的祖先，那么v_i>v_j。
請計算可選的最多的點數，注意這些點不必形成這棵樹的一個連通子樹。
Input
第一行包含一個正整數n(1<=n<=200000)，表示節點的個數。
接下來n行，每行兩個整數v_i,p_i(0<=v_i<=10^9,1<=p_i<i,p_1=0)，表示每個節點的權值與父親。
Output
輸出一行一個正整數，即最多的點數。
Sample Input
6
3 0
1 1
2 1
3 1
4 1
5 1
3 0
1 1
2 1
3 1
4 1
5 1
Sample Output
5
（不）容易看出這是一個變種LIS。
如果只有一條鏈就是LIS。
如果多條鏈但是最終選的點是一條鏈也是個樹版LIS。
然后感受一下這是個LIS。
LIS有一個經典二分做法。
現在我們用set來保存二分做法的那個數組。
不同子樹之間用set來啟發式合并。
然后把這個點權值丟進去替換掉第一個>=它的。
最后輸出set的大小。
?
?一棵樹，每個點u有權值val[u],
要求選出最多的點，并且滿足每個被選的點子樹中沒有權值大于等于該點權值。?
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define rep(i,a,b) for(R i=a;i<=b;i++) 5 #define Rep(i,a,b) for(R i=a;i>=b;i--) 6 #define rp(i,x) for(R i=H[x];i!=-1;i=E[i].nt) 7 #define ms(i,a) memset(a,i,sizeof(a)) 8 #define gc() getchar() 9 template<class T>void read(T &x){ 10 x=0; char c=0; 11 while (!isdigit(c)) c=gc(); 12 while (isdigit(c)) x=x*10+(c^48),c=gc(); 13 } 14 int const maxn=200000+3; 15 multiset<int> s[maxn]; 16 int a[maxn],H[maxn],cnt,n; 17 struct Edge{ 18 int to,nt; 19 }E[maxn]; 20 void add(int a,int b){ 21 E[cnt]=(Edge){b,H[a]};H[a]=cnt++; 22 } 23 void merge(int x,int y){ 24 if(s[x].size()>s[y].size()) swap(s[x],s[y]); 25 multiset<int> :: iterator it=s[x].begin(); 26 for( ; it!=s[x].end(); it++) s[y].insert(*it) ; 27 s[x].clear(); 28 } 29 void dfs(int x){ 30 rp(i,x){ 31 int v=E[i].to; 32 dfs(v); merge(v,x); 33 } 34 multiset<int> :: iterator it=s[x].lower_bound(a[x]); 35 if(it!=s[x].end()) s[x].erase(it); 36 s[x].insert(a[x]); 37 } 38 int main(){ 39 read(n); 40 ms(-1,H); 41 rep(i,1,n){ 42 read(a[i]); 43 int k; read(k); 44 if(k) add(k,i); 45 } 46 dfs(1); 47 printf("%d\n",s[1].size()); 48 return 0; 49 }
?
?
)
