题解：P6534 [COCI 2015/2016 #1] UZASTOPNI

Emplace · 2025-05-15 14:45:56 · 题解

思路

这道题是一道十分巧妙的树形DP。

其中 dpl_{x,i} 表示以结点 x 为根的子树当中，等差数列的首项为 i 是否可行。dpr_{x,i} 表示已结点 x 为根的子树中等差数列末项为 x 为根是否可行。其中 dpl_{x,i} 中的 i 要满足 i \le v_u，dpr_{x,i} 中的 i 要满足 i \ge v_u（题目要求当选了一个结点后必须选它的上司，与就是父亲结点）。

那对于 dpl_{x,i}=1 需要 x 的一个子节点 y 中 dpl_{y,i}=1。然后发现，如果想要让 dpl_{x,i}=1，还需要让 y 的整颗子树能与 x 组成等差数列，并且必须是与笑话编号比 x 小的组成，不然它就无法成为等差数列的首项。既然必须是 x 的首项，那 y 中就必须是末项。

对于 dpr_{x,i} 是一样的，只需把上面全都反过来。

Code

#include<bits/stdc++.h>
using namespace std;
int n,v[20000],h[20000],ne[20000],e[20000],idx,l[20000][200],r[20000][200];
void add(int u,int v){
    e[idx]=v,ne[idx]=h[u],h[u]=idx++;
} 
void dfs(int x){
    vector<int> tl,tr;
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        dfs(j);
        if(v[j]<v[x]) tl.push_back(j);
        if(v[j]>v[x]) tr.push_back(j);
    }
    l[x][v[x]]=1,r[x][v[x]]=1;
    for(int i=v[x]-1;i>=1;i--){
        for(auto p:tl){
            if(l[p][i]){
                for(int j=i;j<v[x];j++){
                    if(r[p][j]&&l[x][j+1]){
                        l[x][i]=1;
                        break;
                    }
                }
            }
        } 
    }
    for(int i=v[x]+1;i<=100;i++){
        for(auto p:tr){
            if(r[p][i]){
                for(int j=v[x]+1;j<=i;j++){
                    if(l[p][j]&&r[x][j-1]){
                        r[x][i]=1;
                        break;
                    }
                }
            }
        } 
    }
}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
    }
    dfs(1);
    int lans=0,rans=0;
    for(int i=1;i<=100;i++){
        lans+=l[1][i];
        rans+=r[1][i]; 
    }
    cout<<lans*rans;
    return 0;
}