Codeforces 490F Treeland Tour 树形dp

Treeland Tour

离散化之后， 每个节点维护上升链和下降链， 感觉复杂度有点高， 为啥跑这么快。。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

int n, tot, ans, r[N], hs[N];

short up[N][N], dn[N][N];

vector<int> G[N];

void dfs(int u, int fa) {

    for(int i = r[u]; i <= tot; i++) up[u][i] = ;

    for(int i = ; i <= r[u]; i++) dn[u][i] = ;

    for(auto& v : G[u]) {

        if(v == fa) continue;

        dfs(v, u);

        int mx1 = , mx2 = ;

        for(int i = ; i <= tot; i++) {

            if(up[v][i] + dn[u][i + ] > ans) ans = up[v][i] + dn[u][i + ];

            if(dn[v][i] + up[u][i - ] > ans) ans = dn[v][i] + up[u][i - ];

        }

        for(int i = ; i <= tot; i++) {

            if(up[v][i] > up[u][i]) up[u][i] = up[v][i];

            if(dn[v][i] > dn[u][i]) dn[u][i] = dn[v][i];

            if(i < r[u] && up[v][i] > mx1) mx1 = up[v][i];

            if(i > r[u] && dn[v][i] > mx2) mx2 = dn[v][i];

        }

        if(mx1 +  > up[u][r[u]]) up[u][r[u]] = mx1 + ;

        if(mx2 +  > dn[u][r[u]]) dn[u][r[u]] = mx2 + ;

        for(int i = ; i <= tot; i++) up[u][i] = max(up[u][i], up[u][i - ]);

        for(int i = tot; i >= ; i--) dn[u][i] = max(dn[u][i], dn[u][i + ]);

    }

    if(up[u][tot] > ans) ans = up[u][tot];

    if(dn[u][] > ans) ans = dn[u][];

}

int main() {

    scanf("%d", &n);

    for(int i = ; i <= n; i++) {

        scanf("%d", &r[i]);

        hs[++tot] = r[i];

    }

    sort(hs + , hs + tot + );

    tot = unique(hs + , hs + tot + ) - hs - ;

    for(int i = ; i <= n; i++)

        r[i] = lower_bound(hs, hs + tot, r[i]) - hs;

    for(int i = ; i <= n; i++) {

        int u, v; scanf("%d%d", &u, &v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(, );

    printf("%d\n", max(, ans));

    return ;

}

/*

*/