选点（dfs+LIS）

题目：

有一棵个节点的二叉树，为根节点，每个节点有一个值。现在要选出尽量多的点。
对于任意一棵子树，都要满足：
如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；
如果在左子树选了一个点，在右子树中选的其他点要比它小；

做法：

题意转化一下。“右子树中选的点要比左子树中选的点小”反一下就是“左子树中选的点要比右子树中选的点大”，而又有“若选根结点，子树内选的点要比根节点大”。
即我们选出的点有如下关系：根右子树左子树。所以要最大化选点的数量，我们只需要后序遍历这棵树得到后序遍历序列，然后跑一个（最长上升子序列）即可。复杂度。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int a[N], T[N][2], dfn[N], tag, te[N];
int dp[N], len;
void dfs(int u){
    dfn[++tag] = a[u];
    if (T[u][1]) dfs(T[u][1]);
    if (T[u][0]) dfs(T[u][0]);
}
int main(void){
    IOS;
    int n; 
    while (cin >> n){
        for (int i = 1; i <= n; ++i) cin >> a[i];    
        for (int i = 1; i <= n; ++i){
            cin >> T[i][0] >> T[i][1];
        }
        tag = 0;
        dfs(1);
        len = 0;
        for (int i = 1; i <= tag; ++i){
            if (!len || dfn[i] > dp[len-1]) dp[len++] = dfn[i];
            else dp[lower_bound(dp, dp+len, dfn[i])-dp] = dfn[i];
        }
        cout << len << endl;
    }
    return 0;
}