2799: [Poi2012]Salaries
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 91 Solved: 54
[Submit][Status][Discuss]
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
HINT
Source
dfs可以求出每个点最大可能是多少。
然后就变成个一个填数问题。
如果$只有一个i，max_i=k$，且1~k之间只剩下了一个数，$v_i=k$
如果$max_i<=k$的数正好填满1~k则清空1~k。
#include<cstdio>
#define N 1000010
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,v[N],f[N],fa[N],mx[N];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int num[N],id[N],all,sum[N];
void dfs(int x)
{
if(mx[x])return;
dfs(fa[x]);
mx[x]=find(mx[fa[x]]-);
if(++num[mx[x]]==)
id[mx[x]]=x;
}
int main()
{
n=read();
for(int i=;i<=n;i++)f[i]=i;
for(int i=;i<=n;i++)
{
fa[i]=read();
v[i]=read();
if(fa[i]==i)v[i]=n;
if(v[i])f[v[i]]=v[i]-,mx[i]=v[i];
}
for(int i=;i<=n;i++)
if(!mx[i])dfs(i);
for(int i=;i<=n;i++)
sum[i]=sum[i-]+(f[i]==i);
for(int i=;i<=n;i++)if(num[i])
{
if(num[i]==&&sum[i]==all+)
v[id[i]]=i,all++;
else if(num[i]+all==sum[i])
all=sum[i];
else num[i+]+=num[i];
}
for(int i=;i<=n;i++)
printf("%d\n",v[i]);
}