Problem – F – Codeforces

（这篇是可以过的做法，上一篇因为常数太大被卡了。）

LIS 问题有一个经典的做法，只需要使用 lower_bound（如果是严格上升的话）就可以实现：

for (int x : some_array)
    *lower_bound(lis, lis + n, x) = x;

实际上这个做法的原理就是时刻维护“长为 $i$ 的上升子序列结尾最小是多少”这一信息。

考虑把原题中“以某个点开头的上升子序列”替换成“以某个点结尾的上升子序列”（比较的时候反过来就行了）。那么不难发现两个 LIS 数组的合并其实就是逐项取 min，所以两个长为 $n, m$ 的 LIS 数组合并只需要 $\min\{n, m\}$ 的时间。（当然加入一个新的元素还是需要 $O(\log n)$ 的时间。）

仍然使用树分治，那么不难发现每个子树中往上走的路径只需要用长链剖分合并就行了。在更新往下走的路径时显然可以用 DFS 实现，退出的时候撤销对 LIS 数组的更改就行了。

和之前的可持久化线段树不太一样的是，这里直接用前缀和后缀来凑的做法不是很管用了（因为合并需要逐项取 min，直接合并复杂度是错的，打标记又比较麻烦）。所以在里面套一个小分治用来处理所有子树，当然还是要特判只有一个子树的情况。

复杂度仍然是 $O(n\log^2 n)$ 的，但常数比可持久化线段树小很多。另外这个做法的空间是 $O(n)$ 的，而可持久化线段树的空间是 $O(n\log n)$的。

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 200005;

struct my_vector {
	vector<int> v;

	my_vector() : v(vector<int>()) {}

	my_vector(const my_vector &o) : v(o.v) {}
	
	pair<int, int> query_and_add(int x) {
		int i = lower_bound(v.begin(), v.end(), x, greater<int>()) - v.begin();

		if (i == (int)v.size())
			v.push_back(0);

		int tmp = v[i];
		v[i] = x;

		return make_pair(i, tmp);
	}

	void undo(pair<int, int> p) {
		int i = p.first, x = p.second;

		if (!x)
			v.pop_back();
		else
			v[i] = x;
	}

	void join(my_vector &o) {
		if ((int)v.size() < (int)o.v.size())
			swap(v, o.v);
		
		for (int i = 0; i < (int)o.v.size(); i++)
			v[i] = min(v[i], o.v[i], greater<int>());
	}
	
	void assign(const my_vector &u, const my_vector &v) {
		this -> v = u.v;
		auto t = v;
		this -> join(t);
	}

	void clear() {
		v.clear();
	}
} dp[maxn];

vector<int> q[maxn];

vector<int> G[maxn];
int a[maxn], ans[maxn];
int pr[maxn], son[maxn], sz[maxn];
bool vis[maxn];

int get_center(int rt) {
	static int qu[maxn];

	int head = 0, tail = 0;
	qu[tail++] = rt;

	while (head != tail) {
		int x = qu[head++];

		sz[x] = 1;

		for (int y : G[x])
			if (y != pr[x] && !vis[y]) {
				pr[y] = x;
				qu[tail++] = y;
			}
	}

	for (int i = tail - 1; i; i--) {
		int x = qu[i];

		sz[pr[x]] += sz[x];
		if (sz[x] > sz[son[pr[x]]])
			son[pr[x]] = x;
	}

	int o = rt;
	while (son[o] && sz[son[o]] * 2 >= sz[rt])
		o = son[o];
	
	for (int i = 0; i < tail; i++) {
		int x = qu[i];

		sz[x] = pr[x] = son[x] = 0;
	}

	return o;
}

void get_dp(int rt) {
	vector<int> &qu = q[rt];
	int head = 0;
	
	qu.push_back(rt);

	while (head != (int)qu.size()) {
		int x = qu[head++];

		for (int y : G[x])
			if (y != pr[x] && !vis[y]) {
				pr[y] = x;
				qu.push_back(y);
			}
	}

	for (int i = head - 1; ~i; i--) {
		int x = qu[i];

		for (int y : G[x])
			if (y != pr[x] && !vis[y])
				dp[x].join(dp[y]);
		
		auto t = dp[x].query_and_add(a[x]);
		ans[x] = max(ans[x], t.first + 1);
	}
}

void dfs(int x, my_vector &v) {
	auto t = v.query_and_add(a[x]);
	ans[x] = max(ans[x], t.first + 1);

	for (int y : G[x])
		if (y != pr[x] && !vis[y])
			dfs(y, v);
	
	v.undo(t);
}

my_vector solve(int x, int l, int r, vector<int> &v) {
	if (l == r)
		return dp[v[l]];
	
	int mid = (l + r) / 2;
	auto left = solve(x, l, mid, v), right = solve(x, mid + 1, r, v);

	auto tl = left.query_and_add(a[x]), tr = right.query_and_add(a[x]);

	for (int i = l; i <= r; i++)
		dfs(v[i], i <= mid ? right : left);

	left.undo(tl);
	right.undo(tr);

	right.join(left);
	return right;
}

void divide_and_conquer(int x) {
	x = get_center(x);

	vis[x] = true;

	vector<int> v;
	for (int y : G[x])
		if (!vis[y]) {
			pr[y] = x;
			v.push_back(y);

			get_dp(y);
		}
	
	ans[x] = max(ans[x], 1);

	if ((int)v.size() < 2) {
		if (!v.empty()) {
			int y = v[0];
			auto p = dp[y].query_and_add(a[x]);
			ans[x] = max(ans[x], p.first + 1);

			my_vector t;
			t.query_and_add(a[x]);
			dfs(y, t);
		}
	}
	else {
		auto t = solve(x, 0, (int)v.size() - 1, v);

		ans[x] = max(ans[x], t.query_and_add(a[x]).first + 1);
	}

	for (int y : v) {
		for (int z : q[y]) {
			pr[z] = sz[z] = 0;
			dp[z].clear();
		}

		q[y].clear();
	}

	for (int y : v)
		divide_and_conquer(y);
}

int main() {

	int T;
	scanf("%d", &T);

	while (T--) {
		int n;
		scanf("%d", &n);

		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		
		for (int i = 1; i < n; i++) {
			int x, y;
			scanf("%d%d", &x, &y);

			G[x].push_back(y);
			G[y].push_back(x);
		}

		divide_and_conquer(1);

		for (int i = 1; i <= n; i++)
			printf("%d\n", ans[i]);
		
		for (int i = 1; i <= n; i++) {
			ans[i] = 0;
			vis[i] = false;
			G[i].clear();
		}
	}

	return 0;
}