题解 P3542 【[POI2012]PEN-Salaries】

skylee · 2017-09-15 13:40:12 · 题解

题目大意：

给定一棵n带权树，每个点的权值在[1,n]范围内且互不相等，并满足子结点的权值一定小于父结点。

现在已知一个包含根结点的联通块中个点的权值，求剩下哪些点的权值能够被求出，并求出这些权值。

思路：

贪心。

很显然，对于某一个结点x，如果当前只有一个可取的权值w，且小于其父结点的权值，那么这个结点的权值一定是w。

事实上所有未知结点权值都可以尝试用这样的方法得出，关键是如何唯一确定下这个权值w。

我们可以用一个数组max记录每个结点权值的上界，再用一个数组last记录小于某个权值能取的最大权值。

max数组可以用一趟DFS递归出来。

然后顺序枚举每一个权值，如果可用就加入到一个“黑箱”中，如果现在黑箱中只有一个权值w并且有未知权值的结点，说明这个节点的权值就是w。

然后如果现在黑箱中有多个权值，未知的结点也很多，那么这些权值就作废。

#include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
    char ch;
    while(!isdigit(ch=getchar()));
    int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int V=1000001;
std::vector<int> c[V];
int n;
int w[V],s[V],par[V],max[V],cnt[V],last[V],root;
int find(const int x) {
    return x==last[x]?x:last[x]=find(last[x]);
}
void dfs(const int x) {
    if(!max[x]) {
        max[x]=find(max[par[x]]-1);
        s[max[x]]=x;
        cnt[max[x]]++;
    }
    for(unsigned i=0;i<c[x].size();i++) {
        dfs(c[x][i]);
    }
}
int main() {
    n=getint();
    for(int i=1;i<=n;i++) last[i]=i;
    for(int i=1;i<=n;i++) {
        int p=getint();
        w[i]=max[i]=getint();
        if(p!=i) {
            c[p].push_back(i);
            par[i]=p;
        } else {
            root=i;
            w[i]=n;
        }
        last[w[i]]=w[i]-1;
    }
    dfs(root);
    for(int i=1,tmp=0;i<=n;i++) {
        if(last[i]==i) tmp++;
        if(cnt[i]&&tmp==1) w[s[i]]=i;
        tmp-=cnt[i];
    }
    for(int i=1;i<=n;i++) printf("%d\n",w[i]);
    return 0;
}