自动搬运

查看原文

来自洛谷，原作者为

	A_Sunny_Day 路漫漫其修远兮，吾将上下而求索

搬运于2025-08-24 22:21:41，当前版本为作者最后更新于2021-08-12 16:30:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[COCI2015-2016#1] UZASTOPNI

题目链接：COCI2015-2016#1UZASTOPNI

​ 写在前面：我代码中数组空间的开大是因为这道题在我们校内 OJ 上加了一个数据更大的点 $1\le n\le10^5,1\le v_i\le2000$。对于这道题来说，可以自行改小。

​ 简化一下题意，意思就是选出来的权值要构成一个连续的序列。这里有一个重要的性质，我们从一棵子树入手，设这棵子树的根为 $rt$ ，它的权值为 $v_{rt}$，我们设它的任意一个儿子为 $son$，接下来我们分类讨论一下它儿子权值的情况。

• $v_{rt}>v_{son}$。

  如果要选择 $son$ 这个点，那么 $rt$ 这个点就一定要选，同时由于集合中不能有相同的权值。所以在 $son$ 为根的子树里面不能选 $v_{rt}$ 这个权值，那么在以 $son$ 为根的子树里面选出权值构成的连续序列的最大值 $v_{max}$ 一定要小于 $v_{rt}$。我们可以用反证法来证明，如果 $v_{max}$ 被选了，由于 $v_{son}<v_{rt}<v_{max}$，为了构成一个连续的序列，我们必须选 $v_{rt}$，而我们又必须选 $rt$，这就矛盾了。

• $v_{rt}<v_{son}$。

  这种情况与上述相似，我们设以 $son$ 为根的子树选出权值构成的连续序列的最小值为 $v_{min}$。如果 $v_{min}<v_{rt}$，又因为 $v_{min}<v_{rt}<v_{son}$，所以以 $son$ 为根的子树里面一定要选 $v_{rt}$，而 $rt$ 也一定要选，这不符合题意，所以 $v_{min}>v_{rt}$。

​ 那么我们得到了一个重要信息：对于一个子树的根 $rt$ 来说，如果选择了它的一个儿子 $son$ ，那么以 $son$ 为根的子树里能构成的连续权值序列是不会跨越 $v_{rt}$ 的。（即最小值大于 $v_{rt}$ 或最大值小于 $v_{rt}$）

​ 根据这个性质我们可以定下我们的 dp 数组。设 $L_{i,j}$ 表示以 $i$ 为根的子树能不能选出一个连续的序列为 ${j,j+1,\dots,v_i}$（$j\le v_i$ 即向左边扩展）。设 $R_{i,j}$ 为以 $i$ 为根的子树能不能选出一个连续的序列为 $v_i,v_i+1,\dots,j$（$v_i\le j$ 即向右边扩展）。然后更新的时候我们要注意我们只将类似于 $[1,2],[3,4]$ 的区间合并，而类似于 $[1,2],[2,3]$ 这类区间我们不合并（因为有重复的权值）。

​ 还有一点需要注意的是，我们 dp 的顺序也有讲究，合并权值小于 $v_{rt}$ 的要按权值降序排序，合并权值大于 $v_{rt}$ 时要按权值升序排序。也就是我们要先合并 $|v_{rt}-v_{son}|$ 较小的儿子。

但是这样我们的时空都是 $O(n\times v)$，对于这道题我们绰绰有余，但是对于我前文提到 $n\le10^5,v\le2000$ 的数据来说是铁定过不了的，这时候我们使用 bitset 进行优化，关于 bitset 这里不再赘述，因为没用 bitset 也能过，有兴趣的读者可以去 oiwiki 自行查看。

​ 那么用 bitset 优化后时空都变成了 $O(\dfrac{n\times v}{w})$。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+5;
int n,v[MAXN];
vector <int> e[MAXN];
bitset<2005> L[MAXN],R[MAXN];
bool cmp(int x,int x_)
{
	return v[x]<v[x_];
}
void dfs(int cur,int fa)
{
	L[cur].set(v[cur]);R[cur].set(v[cur]);
	for(int i=0;i<e[cur].size();++i)
	{
		int to=e[cur][i];
		if(to==fa) continue;
		dfs(to,cur);
	}
	int to;
	for(int i=0;i<e[cur].size();++i)//升序
		if(v[to=e[cur][i]]>v[cur]&&((R[cur]<<1)&L[to]).any()) R[cur]|=R[to];
	for(int i=e[cur].size()-1;i>=0;--i)//降序
		if(v[to=e[cur][i]]<v[cur]&&((L[cur]>>1)&R[to]).any()) L[cur]|=L[to];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]);
	for(int i=1;i<n;++i)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;++i)
		sort(e[i].begin(),e[i].end(),cmp);
	dfs(1,0);
	printf("%lld",(ll)L[1].count()*(ll)R[1].count());
	return 0;
}