给定一棵n个节点的有根树，编号依次为1到n，其中1号点为根节点。每个点有一个权值v_i。 你需要将这棵树转化成一个大根堆。确切地说，你需要选择尽可能多的节点，满足大根堆的性质：对于任意两个点i,j，如果i在树上是j的祖先，那么v_i>v_j。 请计算可选的最多的点数，注意这些点不必形成这棵树的一个连通子树。
（不）容易看出这是一个变种LIS。 如果只有一条链就是LIS。 如果多条链但是最终选的点是一条链也是个树版LIS。 然后感受一下这是个LIS。 LIS有一个经典二分做法。 现在我们用set来保存二分做法的那个数组。 不同子树之间用set来启发式合并。 然后把这个点权值丢进去替换掉第一个>=它的。 最后输出set的大小。
#include<cstdio> #include<algorithm> #include<set> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; const int maxn=200000+10; multiset<int> s[maxn]; int a[maxn],h[maxn],go[maxn],next[maxn]; int i,j,k,l,t,n,m,tot; void add(int x,int y){ go[++tot]=y; next[tot]=h[x]; h[x]=tot; } void merge(int x,int y){ if (s[x].size()>s[y].size()) swap(s[x],s[y]); multiset<int>::iterator it=s[x].begin(); while (it!=s[x].end()){ s[y].insert(*it); it++; } s[x].clear(); } void dfs(int x){ int t=h[x]; while (t){ dfs(go[t]); merge(go[t],x); t=next[t]; } multiset<int>::iterator it=s[x].lower_bound(a[x]); if (it!=s[x].end()) s[x].erase(it); s[x].insert(a[x]); } int main(){ scanf("%d",&n); fo(i,1,n){ scanf("%d%d",&a[i],&j); if (j) add(j,i); } dfs(1); printf("%d\n",s[1].size()); }