【BZOJ2799】[Poi2012]Salaries
Description
给出一棵n个结点的有根树，结点用正整数1~n编号。
每个结点有一个1~n的正整数权值，不同结点的权值不相同，
并且一个结点的权值一定比它父结点的权值大（根结点的权值最大，一定是n）。
现在有些结点的权值是已知的，并且如果一个结点的权值已知，它父结点的权值也一定已知。
问还有哪些结点的权值能够唯一确定。
Input
第一行一个正整数n (n<=1,000,000)，表示树的结点数。
下面共n行，第i行描述编号为i的结点，每行两个整数pi,zi (1<=pi<=n, 0<=zi<=n)。
pi表示结点i的父结点，如果i=pi，说明i是根结点。
当zi>0时，表示结点i的权值已知，并且就是zi；当zi=0时，表示结点i的权值未知。
测试数据保证满足题意，并且存在合法的方案。
Output
输出共n行，依次描述每个结点。如果结点i的权值能够唯一确定，第i行输出结点i的权值，否则第i行输出0。
Sample Input
10
2 2
2 10
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0
2 2
2 10
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0
Sample Output
2
2
10
1
9
5
8
0
0
0
0
2
10
1
9
5
8
0
0
0
0
题解：这题做法好神啊。。
一个点的权值唯一确定等价于x>=val且x<=val，那么怎么求最大值呢？如果它父亲的最大值为val，那么从val-1往下找，找到第一个没有被占用的权值就是当前点的最大值。然后怎么求最小值呢？
我们将所有点按最大值排序，然后从小往大一个一个确定每个点。如果有多个点的最大值=i，那么这些点都无法被确定。如果只有一个点的最大值=i，并且以前已经确定<=i-1的数有i-1个，那么这个点可以被唯一确定。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1000010;
int n,rt,cnt,sum,tot;
int fa[maxn],to[maxn],next[maxn],head[maxn],v[maxn],ch[maxn],mx[maxn];
struct node
{
int mx,org;
}s[maxn];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
inline void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x,int mxx)
{
if(!v[x]) s[++tot].mx=mxx,s[tot].org=x;
for(int i=head[x];i!=-1;i=next[i])
{
if(!v[to[i]]) dfs(to[i],mx[mxx-1]);
else dfs(to[i],v[to[i]]);
}
}
bool cmp(const node &a,const node &b)
{
return a.mx<b.mx;
}
int main()
{
n=rd();
int i,j,tmp;
memset(head,-1,sizeof(head));
for(i=1;i<=n;i++) mx[i]=i;
for(i=1;i<=n;i++)
{
fa[i]=rd(),v[i]=rd(),mx[v[i]]=0;
if(fa[i]==i) rt=i,fa[i]=0;
else add(fa[i],i);
}
for(i=1;i<=n;i++) if(!mx[i]) mx[i]=mx[i-1];
dfs(rt,n);
sort(s+1,s+tot+1,cmp);
for(i=j=1;i<=n;i++)
{
if(mx[i]!=i) sum++;
else
{
tmp=0;
for(;j<=tot&&s[j].mx==i;j++,tmp++);
if(tmp==1&&sum==i-1) v[s[j-1].org]=i;
sum+=tmp;
}
}
for(i=1;i<=n;i++) printf("%d\n",v[i]);
return 0;
}