题解：P3542 [POI 2012] PEN-Salaries

huangenning · 2025-08-27 22:36:11 · 题解

题目思路

自己造几棵树后可发现，每个结点都有最大可能权值。这个最大可能权值取决于其父亲的权值以及其它点是否占用某些权值。设第 i 个点的最大可能权值为 r[i]。可以决定每个点的权值是否唯一只需要看最大权值在 r[i] 以内的结点个数是否刚好等于 n（如果 ≠n 即表示有滑动空间）以及最大权值等于 r[i] 的个数是否等于 1（若 ≠1 则有两数可互换位置）即可。

有了这个思路后，我们可以先做一次从根部开始的 dfs 求所有 r[i], 对于每个点，如果其已有 z[i]，则 r[i]=z[i]；否则应为其父节点最大权值-1（即 r[i]=r[p[i]]-1）, 接着如果现在的 r[i] 已经有某个 z 占了，r[i] 应该一直减，直到未被任何 z 占领。然后用 s[i] 求出最大权值 ≤i 的点数量。对于每个点，若 s[r[i]]-s[r[i]-1]=1 且 s[r[i]]=r[i] 即可确定其唯一权值为 r[i]，否则无法确定。

丑陋代码

#include<iostream>
#include<cstdio>
using namespace std;
const int NR=1000001;
bool f[NR];
int cnt,p[NR],z[NR],r[NR],s[NR],hed[NR],nxt[2*NR],to[2*NR];
void ad(int u,int v)
{
    cnt++;
    to[cnt]=v;
    nxt[cnt]=hed[u];
    hed[u]=cnt;
    return;
}
void dfs(int x)
{
    if(z[x]) r[x]=z[x];
    else
    {
        r[x]=r[p[x]]-1; 
        while(f[r[x]]) r[x]--;
    }
    s[r[x]]++;
    int i;
    for(i=hed[x];i;i=nxt[i]) dfs(to[i]);
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,i,fa;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>p[i]>>z[i];
        if(p[i]==i)
        {
            z[i]=n;
            fa=i;
        }
        else ad(p[i],i);
        f[z[i]]=true;
    }
    dfs(fa);
    for(i=1;i<=n;i++) s[i]+=s[i-1];
    for(i=1;i<=n;i++)
        if(!z[i] && s[r[i]]-s[r[i]-1]==1 && s[r[i]]==r[i]) z[i]=r[i];
    for(i=1;i<=n;i++) cout<<z[i]<<endl;
    return 0;
}

注意事项

1、题目未说明，所以可能存在所有点输入的 z[i] 都等于 0 的情况，此时需对根节点进行 z[i] = n, 否则会 RTE。

2、输入量较大，若不进行输入优化，会 TLE 掉一个测试点。