[COCI2015-2016#1] UZASTOPNI

A_Sunny_Day · 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，接下来我们分类讨论一下它儿子权值的情况。

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