题解：P15875 [ICPC 2026 NAC] Acorn Quarrels

Aux_sky · 2026-10-19 16:15:07 · 题解

小清新构造题。

题意

给定一棵树，要求给树上每个点赋一个点权 v_i，满足对于 1\le i \le n 从小到大依次执行如下操作后每个位置点权不变。

设当前 i 的邻点的点权最大值为 k，对于每一个与 i 相连的点 u，若 v_u=k，v_u=v_u-1,v_i=v_i+1。

Solution

这个限制不太好做，考虑强化一下限制。

我们令 i 在操作的时候所有邻点的点权都相等，这样操作就相当于 v_i=v_i+deg_i，并把所有相邻点的点权都减一。

容易发现操作完之后每个位置的点权确实是不变的，因为减了 deg_i 次并加了 deg_i 就抵消了。

我们发现这个东西是很好构造的，考虑从根往下递推。

一个点 u 在 t 操作时的权值为：

我们已经知道了当前点 u 的父亲在 u 操作时的权值为 h，则所有 u 的儿子在 u 操作时的权值也为 h，从而可以推出每个儿子初始时的权值 h'，然后继续递推下去即可。

容易发现总能构造出一组解并且 v_{\max}-v_{\min}<n，把每个 v 调整到 [n,2n-1] 即可。

::::success[Code]

int w[N],n,mn=1e9;
vector<int>e[N];
int col(int u,int t){
    int res=w[u];
    int h=lower_bound(e[u].begin(),e[u].end(),t)-e[u].begin();
    if(u>=t)return res-h;
    return res-h+e[u].size();
}
int d(int u,int t,int p){
    int h=lower_bound(e[u].begin(),e[u].end(),t)-e[u].begin();
    if(u>=t)return p+h;
    return p-e[u].size()+h;
}
void dfs(int u,int fa){
    int h=col(fa,u);
    for(auto v : e[u]){
        if(v==fa)continue;
        w[v]=d(v,u,h);
        dfs(v,u);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1,u,v;i<n;++i){
        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());
    dfs(1,0);
    for(int i=1;i<=n;++i)mn=min(mn,w[i]);
    mn=n-mn;
    for(int i=1;i<=n;++i)printf("%d ",w[i]+mn);
    return 0;
}

::::