题解：P14157 [ICPC 2022 Nanjing R] 树的染色

· · 题解

来个比较暴力的做法。

思路

首先一次操作只会影响同层的点，于是我们逐层考虑。

对于一层，一定形如划分为若干段，每一段由这一段的 \operatorname{LCA} 及其祖先操作得来，因此一段的贡献可以用个数据结构维护，有经典结论区间 \operatorname{LCA} 的深度等于 \min\limits_{i\in[l,r)}dep_{lca(i,i+1)} 于是数据结构优化 dp 即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
int read(){int p=0,flg=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*flg;}
int T,n,a[100010],f[100010][21],dep[100010],dp[100010],b[100010],st[100010],top;vector<int>e[100010],D[100010];
struct Segtree{
    int n,t[200010];
    void init(int N){n=N;for(int i=1;i<(n<<1);i++) t[i]=1e9;}
    void modify(int l,int r,int v){
        for(l+=n-1,r+=n;l<r;l>>=1,r>>=1){
            if(l&1) t[l]=min(t[l],v),l++;
            if(r&1) r--,t[r]=min(t[r],v);
        }
    }
    int query(int x){int res=t[x+=n-1];while(x>>=1) res=min(res,t[x]);return res;}
}A;
struct SegtreeB{
    struct seg{int l,r,mi,tag;}t[400010];
    #define lson now<<1
    #define rson now<<1|1
    void build(int now,int l,int r){
        t[now]={l,r};if(l==r){t[now].mi=1e9;return ;}
        int mid=(l+r)>>1;build(lson,l,mid);build(rson,mid+1,r);t[now].mi=min(t[lson].mi,t[rson].mi);
    }
    void puttag(int now,int v){t[now].mi+=v;t[now].tag+=v;}
    void pushdown(int now){if(!t[now].tag) return ;puttag(lson,t[now].tag);puttag(rson,t[now].tag);t[now].tag=0;}
    void modify(int now,int x,int v){
        if(t[now].l==t[now].r){t[now].mi=v;return ;}
        pushdown(now);int mid=(t[now].l+t[now].r)>>1;if(x<=mid) modify(lson,x,v);else modify(rson,x,v);t[now].mi=min(t[lson].mi,t[rson].mi);
    }
    void modify(int now,int l,int r,int v){
        if(l<=t[now].l&&t[now].r<=r){puttag(now,v);return ;}
        pushdown(now);int mid=(t[now].l+t[now].r)>>1;if(l<=mid) modify(lson,l,r,v);if(mid<r) modify(rson,l,r,v);t[now].mi=min(t[lson].mi,t[rson].mi);
    }
}B;
void solve(){
    n=read();for(int i=0;i<n;i++) a[i]=read();for(int i=1;i<=n;i++) e[i].clear(),D[i].clear();for(int i=1;i<n;i++){int u=read(),v=read();e[u].push_back(v);e[v].push_back(u);}
    function<void(int,int)>dfs=[&](int u,int fa){
        D[dep[u]=dep[fa]+1].push_back(u);f[u][0]=fa;for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
        for(auto v:e[u]) if(v^fa) dfs(v,u);
    };dfs(1,0);
    auto lca=[&](int u,int v){
        if(dep[u]<dep[v]) swap(u,v);for(int i=20;~i;i--) if(dep[u]-(1<<i)>=dep[v]) u=f[u][i];if(u==v) return u;
        for(int i=20;~i;i--) if(f[u][i]^f[v][i]) u=f[u][i],v=f[v][i];return f[u][0];
    };
    A.init(n);int ans=0;for(int d=1;d<=n;d++) if(!D[d].empty()){
        A.modify(1,d,a[d-1]);B.build(1,1,D[d].size());top=0;for(int i=1;i<D[d].size();i++) b[i]=dep[lca(D[d][i-1],D[d][i])];
        dp[1]=A.query(1);B.modify(1,1,0);for(int i=2;i<=D[d].size();i++){
            while(top&&b[st[top]]>b[i-1]) B.modify(1,st[top-1]+1,st[top],-A.query(d-b[st[top]]+1)),top--;
            B.modify(1,st[top]+1,i-1,A.query(d-b[i-1]+1));st[++top]=i-1;
            dp[i]=min(dp[i-1]+A.query(1),B.t[1].mi);B.modify(1,i,dp[i-1]);
        }ans+=dp[D[d].size()];
    }cout<<ans<<'\n';
}
signed main(){
    T=read();while(T--) solve();
    return 0;
}