Problem – F – Codeforces

题意：给定一棵有点权的树，对每个点计算：从这个点开始走，能走出的所有简单路径，形成的点权序列的最长上升子序列（当然要包含自己）的长度的最大值。

$n\le 2 \times 10 ^ 5$

如果不分治的话，直接按照点权排序之后会发现要维护一个以入边为状态的 DP。这个东西的复杂度是和度数的平方有关的，并且没法优化。所以考虑点分治。

在处理某层时可能有多棵子树，为了保证复杂度需要再写一个小分治用来处理这些子树之间的转移（并且记得加上分治中心之后再去更新答案）。

另外有一个细节，如果只有一棵子树，那么需要特殊处理，用分治中心更新一下这棵子树中，否则按照代码的写法会漏掉。

线段树合并做法被卡了，题解说启发式合并可以过。待补。

UPD:傻了，分治内部是不用写小分治的，直接用前缀和后缀就可以凑出“除去某个子树”的信息了。更改的只有这一小段，其他的和下面的代码一样。

void dfs(int x, int seg, int pre, int suf) {
	dp_down[x] = max(query(1, N, seg, a[x] + 1), max(query(1, N, pre, a[x] + 1), query(1, N, suf, a[x] + 1))) + 1;
	seg = modify_add(1, N, seg, a[x], dp_down[x]);

	ans[x] = max(ans[x], dp_down[x]);

	for (int y : G[x])
		if (y != pr[x] && !vis[y])
			dfs(y, seg, pre, suf);
}

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

	// printf("--- divide_and_conquer(%d) ---\n", x);

	vis[x] = true;

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

	ans[x] = max(ans[x], 1);

	if (m <= 1) {
		if (m) {
			ans[x] = max(ans[x], query(1, N, root[v[0]], a[x] + 1) + 1);

			int seg = modify_add(1, N, 0, a[x], 1);

			dfs(v[0], seg, 0, 0);
		}
	}
	else {
		vector<int> suf(m);
		
		int last = 0;
		for (int i = m - 1; ~i; i--)
			last = suf[i] = merge(1, N, last, root[v[i]]);

		last = 0;

		for (int i = 0; i < m; i++) {
			int su = i < m - 1 ? suf[i + 1] : 0, cnt = seg_cnt;

			int tmp = max(query(1, N, su, a[x] + 1), query(1, N, last, a[x] + 1)) + 1;
			dfs(v[i], modify_add(1, N, 0, a[x], tmp), last, su);

			seg_clear(cnt);

			ans[x] = max(ans[x], tmp);

			last = merge(1, N, last, root[v[i]]);
		}
	}

	seg_clear();

	for (int y : v) {
		for (int z : que[y]) {
			dp_up[z] = dp_down[z] = 0;
			pr[z] = 0;
			root[z] = 0;
		}

		que[y].clear();
	}

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

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 200005, maxm = maxn * 19 * 2;

int val[maxm], lc[maxm], rc[maxm], seg_cnt;

int merge(int l, int r, int x, int y) {
	if (!x || !y)
		return x | y;
	
	int z = ++seg_cnt;

	val[z] = max(val[x], val[y]);

	if (l < r) {
		int mid = (l + r) / 2;

		lc[z] = merge(l, mid, lc[x], lc[y]);
		rc[z] = merge(mid + 1, r, rc[x], rc[y]);
	}

	return z;
}

int modify_add(int l, int r, int u, int p, int d) {
	int o = ++seg_cnt; // 持久化
	lc[o] = lc[u];
	rc[o] = rc[u];
	
	val[o] = max(val[u], d);

	if (l < r) {
		int mid = (l + r) / 2;
		
		if (p <= mid)
			lc[o] = modify_add(l, mid, lc[o], p, d);
		else
			rc[o] = modify_add(mid + 1, r, rc[o], p, d);
	}

	return o;
}

int query(int l, int r, int o, int s) {
	if (s > r)
		return 0;

	if (!o || s <= l)
		return val[o];
	
	int mid = (l + r) / 2, ans = query(mid + 1, r, rc[o], s);
	
	if (s <= mid)
		ans = max(ans, query(l, mid, lc[o], s));
	
	return ans;
}

void seg_clear() {
	for (int *a : {val, lc, rc})
		memset(a, 0, sizeof(int) * (seg_cnt + 1));

	seg_cnt = 0;
}

void seg_clear(int until) {
	for (int *a : {val, lc, rc})
		memset(a + until + 1, 0, sizeof(int) * (seg_cnt - until));

	seg_cnt = until;
}

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

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

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

	while (head != tail) {
		int x = q[head++];
		sz[x] = 1;
		son[x] = 0;

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

	for (int i = tail - 1; i; i--) {
		int x = q[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 = q[i];
		sz[x] = pr[x] = son[x] = 0;
	}

	return o;
}

int root[maxn];

int a[maxn];
int dp_up[maxn], dp_down[maxn]; // go up, or go down
int ans[maxn], N;

vector<int> que[maxn];

void prework(int rt) {
	vector<int> &q = que[rt];

	int head = 0;
	q.push_back(rt);

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

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

	for (int i = (int)q.size() - 1; ~i; i--) {
		int x = q[i];

		for (int y : G[x])
			if (y != pr[x] && !vis[y])
				root[x] = merge(1, N, root[x], root[y]);
		
		dp_up[x] = query(1, N, root[x], a[x] + 1) + 1;
		root[x] = modify_add(1, N, root[x], a[x], dp_up[x]);

		ans[x] = max(ans[x], dp_up[x]);
	}
}

void dfs(int x, int seg) {
	dp_down[x] = query(1, N, seg, a[x] + 1) + 1;
	seg = modify_add(1, N, seg, a[x], dp_down[x]);

	ans[x] = max(ans[x], dp_down[x]);

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

int solve(int x, vector<int> &v, int l, int r) {
	if (l == r)
		return root[v[l]];
	
	int mid = (l + r) / 2;
	
	int seg[2] = {solve(x, v, l, mid), solve(x, v, mid + 1, r)};
	int cnt = seg_cnt;

	int st[2];
	for (int i = 0; i < 2; i++) {
		int tmp = query(1, N, seg[i], a[x] + 1) + 1;
		ans[x] = max(ans[x], tmp);

		st[i] = modify_add(1, N, seg[i], a[x], tmp);
	}

	for (int i = l; i <= r; i++)
		dfs(v[i], st[i <= mid]);
	
	seg_clear(cnt);
	
	return merge(1, N, seg[0], seg[1]);
}

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

	vis[x] = true;

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

	ans[x] = max(ans[x], 1);

	if (m <= 1) {
		if (m) {
			ans[x] = max(ans[x], query(1, N, root[v[0]], a[x] + 1) + 1);

			int seg = modify_add(1, N, 0, a[x], 1);

			dfs(v[0], seg);
		}
	}
	else {
		int seg = solve(x, v, 0, m - 1);

		ans[x] = max(ans[x], query(1, N, seg, a[x] + 1) + 1);
	}

	seg_clear();

	for (int y : v) {
		for (int z : que[y]) {
			dp_up[z] = dp_down[z] = 0;
			pr[z] = 0;
			root[z] = 0;
		}

		que[y].clear();
	}

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

int b[maxn];

int main() {

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

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

		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		
		memcpy(b + 1, a + 1, sizeof(int) * n);

		sort(b + 1, b + n + 1);

		for (int i = 1; i <= n; i++)
			a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
		
		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();
		}

		assert(seg_cnt == 0);
	}

	return 0;
}