题解 CF627D 【Preorder Test】

· · 题解

题解地址：

[CF627D]Preorder Test - skylee's Blog

题目大意：

一个n(n\le2\times10^5)个结点的树，每个结点有一个权值w_i。可以任选一点为根，并选择一些结点交换其子结点的顺序，使得该树DFS序上第m个结点的权值最大。求最大权值。

思路：

二分答案k ，树形DP检验可行性。
对于以结点x为根的子树，用f[x]表示x的子树经过任意变换的所有DFS序中，满足w_i\ge k的最长前缀长度。
若w_x<k，则f[x]显然为0。
若w_x\ge k，则对于x的每个子结点y，若f[y]=size[y]，将y的子树插入到x子树DFS序的最前面仍然是合法的；而对于所有满足f[y]<size[y]的子结点y，可以选择一个f[y]最大的加入。考虑以x为根的情况，则只需要在f[x]上加上满足f[y]<size[y]的f[y]第二大的f[y]。此时不需要考虑加上的会是x上方的点，因为加上x上方的点的情况肯定能在x上方的点处统计到。
时间复杂度O(n)。

源代码：

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<forward_list>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=2e5+1;
int w[N],f[N],k,size[N],ans,root;
std::forward_list<int> e[N];
inline void add_edge(const int &u,const int &v) {
    e[u].push_front(v);
    e[v].push_front(u);
}
void dfs(const int &x,const int &par) {
    f[x]=size[x]=1;
    int max1=0,max2=0;
    for(register auto &y:e[x]) {
        if(y==par) continue;
        dfs(y,x);
        size[x]+=size[y];
        if(f[y]==size[y]) {
            f[x]+=f[y];
        } else {
            if(f[y]>max1) std::swap(f[y],max1);
            if(f[y]>max2) std::swap(f[y],max2);
        }
    }
    f[x]=w[x]<k?0:f[x]+max1;
    ans=std::max(ans,f[x]+max2);
}
inline int calc() {
    dfs(root,ans=0);
    return ans;
}
int main() {
    const int n=getint(),m=getint();
    for(register int i=1;i<=n;i++) w[i]=getint();
    for(register int i=1;i<n;i++) {
        add_edge(getint(),getint());
    }
    root=std::min_element(&w[1],&w[n]+1)-w;
    int l=*std::min_element(&w[1],&w[n]+1);
    int r=*std::max_element(&w[1],&w[n]+1);
    while(l<=r) {
        k=(l+r)>>1;
        if(calc()>=m) {
            l=k+1;
        } else {
            r=k-1;
        }
    }
    printf("%d\n",l-1);
    return 0;
}