题面
给定一棵\(n\)个节点的有根树，编号依次为\(1\)到\(n\)，其中\(1\)号点为根节点。每个点有一个权值\(v_i\)。
选择尽可能多的节点，使对于任意两个点\(i,j\)，如果\(i\)在树上是\(j\)的祖先，那么\(v_i>v_j\)。 请计算可选的最多的点数，注意这些点不必形成这棵树的一个连通子树。\(n\leq2*10^5\)
解析
这题无非想让选出的这些点自下往上都能构成最长上升子序列。
于是自下往上每条链都维护一下最长上升子序列。 如果两链相交，把两条序列直接合并（因不影响答案）。 然后尝试把交点（\(LCA\)）加入序列即可。
关键是怎么维护这东西。
线段树合并？？？怒码\(3KB\)？？？\(set\)神器拯救一切。 而且由于合并时两链（树）互不影响，可以启发式合并。（如果父亲已有序列长度小于儿子，可以父子完全交换）。 复杂度\(O(nlog^2n)\)。#include#include #include #include #include #include #include #include #define re register#define il inline#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;const int mod=1e9+7,N=2e5+100,M=3000;struct Edge{int to,nxt;}e[N<<1];int n,h[N],cnt,w[N];multiset f[N];il void add(re int u,re int v){ e[++cnt]=(Edge){v,h[u]};h[u]=cnt; e[++cnt]=(Edge){u,h[v]};h[v]=cnt;}il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il void dfs(re int u,re int fa){ for(re int i=h[u];i+1;i=e[i].nxt) { re int v=e[i].to; if(v==fa) continue; dfs(v,u); if(f[v].size()>f[u].size()) swap(f[v],f[u]); for(set ::iterator j=f[v].begin();j!=f[v].end();j++) f[u].insert(*j); f[v].clear(); } if(f[u].size()>0&&f[u].lower_bound(w[u])!=f[u].end()) f[u].erase(f[u].lower_bound(w[u])); f[u].insert(w[u]);}int main(){ memset(h,-1,sizeof(h)); n=gi(); fp(i,1,n) w[i]=gi(),add(i,gi()); dfs(1,0); printf("%lld\n",1ll*f[1].size()); return 0;}