CF796C Bank Hacking

题目传送门

思路

放眼整个题解区没有我这种解法，因此来写一篇题解。

既然要求我们选择一个节点作为根，那么我们就枚举根。

接下来的问题就是如何 \(\mathcal{O}(1)\) 或 \(\mathcal O(\log n)\) 计算贡献。

我们可以把节点分为四类：这个节点，这个节点的父亲，这个节点的儿子，另外的节点。

其中第 \(1/2\) 类非常容易解决。难解决的就是这个节点的儿子和另外的节点。

不妨考虑线段树，把这个节点所有的儿子压到一个区间内，为此，我们需要寻找一种新的编号方式。

原本正常把树拍扁都是根据 \(\mathcal DFS\) 序遍历的，现在我们需要以 \(\mathcal BFS\) 序遍历，而且以点 \(i\) 为根时，它原本的父亲 \(fa_i\) 也会变成它的儿子。

于是如此模拟即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

int const N=1e6+10;

int n,go[N];

struct node{int w,id;}a[N];

int vis[N],fa[N],minx[N],maxx[N],c[N];

vector<int>b[N];

struct Segment_Tree{

    #define ls (x<<1)

    #define rs (x<<1|1)

    #define mid ((l+r)>>1)

    int c[N<<2];

    inline void build(int x,int l,int r){

        if (l==r){c[x]=a[l].w;return;}

        build(ls,l,mid);build(rs,mid+1,r);

        c[x]=max(c[ls],c[rs]);

    }

    inline void update(int x,int l,int r,int p,int v){

        if (l==r){c[x]=v;return;}

        if (p<=mid) update(ls,l,mid,p,v);

        else update(rs,mid+1,r,p,v);

        c[x]=max(c[ls],c[rs]);

    }

    inline int query(int x,int l,int r,int ll,int rr){

        if (ll<=l && r<=rr) return c[x];

        int res=-2e9;

        if (ll<=mid) res=max(res,query(ls,l,mid,ll,rr));

        if (mid<rr) res=max(res,query(rs,mid+1,r,ll,rr));

        return res;

    }

}T;

inline bool cmp(node x,node y){return x.id<y.id;}

inline int solve(int x){

    int la=0;

    if (fa[x]) la=c[fa[x]],T.update(1,1,n,go[fa[x]],-2e9);

    T.update(1,1,n,go[x],-2e9);

    int res=c[x];

    if (minx[x]<=maxx[x]) res=max(res,T.query(1,1,n,minx[x],maxx[x])+1);

    if (minx[x]-1>=1) res=max(res,T.query(1,1,n,1,minx[x]-1)+2);

    if (maxx[x]+1<=n) res=max(res,T.query(1,1,n,maxx[x]+1,n)+2);

    if (fa[x]) res=max(res,la+1),T.update(1,1,n,go[fa[x]],la);

    T.update(1,1,n,go[x],c[x]);

    return res;

}

signed main(){

    ios::sync_with_stdio(false);

    cin.tie(0),cout.tie(0);

    cin>>n;

    for (int i=1;i<=n;++i) cin>>a[i].w,c[i]=a[i].w;

    queue<int>q;

    for (int i=1;i<n;++i){

        int u,v;cin>>u>>v;

        b[u].push_back(v);

        b[v].push_back(u);

    }

    q.push(1);vis[1]=1;a[1].id=1;

    int cnt=1;

    while (!q.empty()){

        int x=q.front();q.pop();

        minx[x]=cnt+1;vis[x]=1;

        for (auto v:b[x]){

            if (vis[v]) continue;

            fa[v]=x;

            a[v].id=++cnt;q.push(v);

        }

        maxx[x]=cnt;

    }

    for (int i=1;i<=n;++i) go[i]=a[i].id;

    sort(a+1,a+n+1,cmp);

    T.build(1,1,n);

    int ans=9e18;

    for (int i=1;i<=n;++i) ans=min(ans,solve(i));

    cout<<ans<<'\n';

    return 0;

}

巴特西

CF796C Bank Hacking

思路

代码

最新文章

热门文章