Description

给你一个有 $n$ 个点的树，第 $i$ 个点有一个点权 $a_i$，定义 $f_i$ 表示从根节点到 $i$ 号点的简单路径上点权的最长单调不下降子序列的长度，现在请你求出 $f_i$ 的最大值。

$1 \leq n \leq 10^5, 1 \leq |a_i| \leq 10^9$

Solution

比赛的时候快写完了才被告知这题是原题，因此被换掉了。但还是不想浪费写了的代码，感觉比较正确，来写篇题解。

考虑怎么快速求出 $f_i$。观察 $f_i$ 的转移式：

$f_i = f_j + 1 (a_i \geq a_j)$

并且点 $j$ 在根节点到点 $i$ 的路径上。

对于 $a_i \geq a_j$ 的这一个限制条件，我们排序后用一棵 线段树 来求最小值即可。

对于「点 $j$ 在根节点到点 $i$ 的路径上」这个限制条件，用 树链剖分 即可解决。

对于 $a_i = a_j$ 的情况，在排序的时候对于 $a_i$ 相同的，DFS 序小的排在前面即可，这样就可以一个一个按照顺序来加了。

Code

#include <cstdio>
#define maxN 100010
struct read{ int v, x, q; } p[maxN];
struct tree{ int max; } a[maxN << 3];
struct edge{ int x, y, g; } b[maxN << 1];
int len = 0, n = 0;
int dp[maxN], h[maxN];
int number[maxN], top[maxN];
int size[maxN], dep[maxN], son[maxN], fa[maxN];
int Max (int x, int y)
{
	return x > y ? x : y;
}
void ins (int x, int y)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].g = h[x];
	h[x] = len;
}
void px (int l, int r)
{
	int x = l, y = r, mid1 = p[(l + r) >> 1].v, mid2 = p[(l + r) >> 1].q;
	while(x <= y)
	{
		while(p[x].v < mid1 || (p[x].v == mid1 && p[x].q < mid2))
		{
			x++;
		}
		while(p[y].v > mid1 || (p[y].v == mid1 && p[y].q > mid2))
		{
			y--;
		}
		if(x <= y)
		{
			read t = p[x];
			p[x] = p[y];
			p[y] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px(l, y);
	}
	if(x < r)
	{
		px(x, r);
	}
}
void build (int now, int l, int r)
{
	a[now].max = 0;
	if(l != r)
	{
		int mid = (l + r) >> 1;
		build(now << 1, l, mid);
		build(now << 1 | 1, mid + 1, r);
	}
}
void dfs1 (int x)
{
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(!dep[y])
		{
			fa[y] = x;
			dep[y] = dep[x] + 1;
			dfs1(y);
			if(size[y] > size[son[x]])
			{
				son[x] = y;
			}
			size[x] += size[y];
		}
	}
	size[x]++;
}
void dfs2 (int x)
{
	number[x] = ++number[0];
	if(son[x])
	{
		top[son[x]] = top[x];
		dfs2(son[x]);
	}
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(dep[y] == dep[x] + 1 && y != son[x])
		{
			top[y] = y;
			dfs2(y);
		}
	}
}
void change (int now, int l, int r, int x, int t)
{
	if(l == r)
	{
		a[now].max = t;
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid)
	{
		change(now << 1, l, mid, x, t);
	}
	else
	{
		change(now << 1 | 1, mid + 1, r, x, t);
	}
	a[now].max = Max(a[now << 1].max, a[now << 1 | 1].max);
}
int query (int now, int l, int r, int L, int R)
{
	if(l == L && r == R)
	{
		return a[now].max;
	}
	int mid = (l + r) >> 1;
	if(R <= mid)
	{
		return query(now << 1, l, mid, L, R);
	}
	else if(mid + 1 <= L)
	{
		return query(now << 1 | 1, mid + 1, r, L, R);
	}
	else
	{
		int A = query(now << 1, l, mid, L, mid);
		int B = query(now << 1 | 1, mid + 1, r, mid + 1, R);
		return Max(A, B);
	}
}
int MAX (int x)
{
	int ans = 0;
	while(x)
	{
		ans = Max(ans, query(1, 1, n, number[top[x]], number[x]));
		x = fa[top[x]];
	}
	return ans;
}
int main ()
{
	scanf("%d", &n);
	for(int i = 2;i <= n; i++)
	{
		int x = 0;
		scanf("%d", &x);
		ins(x, i);
	}
	int root = 1;
	dep[root] = 1;
	dfs1(root);
	top[root] = root;
	dfs2(root);
	for(int i = 1;i <= n; i++)
	{
		scanf("%d", &p[i].v);
		p[i].x = i;
		p[i].q = number[i];
	}
	px(1, n);
	build(1, 1, n);
	for(int i = 1;i <= n; i++)
	{
		dp[p[i].x] = MAX(p[i].x) + 1;
		change(1, 1, n, number[p[i].x], dp[p[i].x]);
	}
	int Ans = 0;
	for(int i = 1;i <= n; i++)
	{
		Ans = Max(Ans, dp[i]);
	}
	printf("%d", Ans);
	return 0;
}

abcdeffa's Blog

GMOJ S4280 【抓知了】

Description

Solution

Code