ABC165F LIS on Tree の解説のような何か

この問題割と好き (まあ、好きじゃなかったら記事書かない気がする)

atcoder.jp

問題

各頂点に整数が書かれた木が与えられる。 各 について、次を求めよ。

• 頂点 から頂点 までのパス上の整数列の、LIS (最長増加部分列) の長さ

制約

• 

前提 (普通の LIS)

次(リンク)のような問題を考えます。

onlinejudge.u-aizu.ac.jp

この問題はDPで で解くことができます。二分探索を用いる解法とセグメント木 (若しくはBIT) を用いる解法があります。詳しい解法については、調べましょう。(丸投げ)

二分探索解をこの後使うので、一応実装を書きます。

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1 << 30;

int N, A[100009];
int dp[100009];

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> A[i];

    fill(dp, dp + N, INF);

    for(int i = 0; i < N; i++)
        *lower_bound(dp, dp + N, A[i]) = A[i];

    cout << lower_bound(dp, dp + N, INF) - dp << endl;

    return 0;
}

本題

先ほどの実装で各 での DP 配列の書き換え回数が だったことに注目します。

書き換えが なので、元の値を覚えておいて、その値に戻すのも でできます。

よって、DP 配列を適宜更新したり元の値にもどしたりしながら木の上を dfs することで、全体で 時間で解けます。

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1 << 30;

int N, a[200009];
vector<int> G[200009];
int dp[200009];
int ans[200009];

void dfs(int v, int p) {
    int *it = lower_bound(dp, dp + N, a[v]);
    swap(*it, a[v]);

    ans[v] = lower_bound(dp, dp + N, INF) - dp;

    for(int u : G[v])
        if(u != p) dfs(u, v);

    swap(*it, a[v]);
}

int main() {
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> a[i];
    for(int i = 1; i < N; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    fill(dp, dp + N, INF);

    dfs(1, -1);

    for(int i = 1; i <= N; i++)
        cout << ans[i] << endl;

    return 0;
}