2799: [Poi2012]Salaries
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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。
1 #include<cstdio> 2 #define N 1000010 3 inline int read() 4 { 5 int x=0,f=1;char ch=getchar(); 6 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 8 return x*f; 9 } 10 int n,v[N],f[N],fa[N],mx[N]; 11 inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);} 12 int num[N],id[N],all,sum[N]; 13 void dfs(int x) 14 { 15 if(mx[x])return; 16 dfs(fa[x]); 17 mx[x]=find(mx[fa[x]]-1); 18 if(++num[mx[x]]==1) 19 id[mx[x]]=x; 20 } 21 int main() 22 { 23 n=read(); 24 for(int i=1;i<=n;i++)f[i]=i; 25 for(int i=1;i<=n;i++) 26 { 27 fa[i]=read(); 28 v[i]=read(); 29 if(fa[i]==i)v[i]=n; 30 if(v[i])f[v[i]]=v[i]-1,mx[i]=v[i]; 31 } 32 for(int i=1;i<=n;i++) 33 if(!mx[i])dfs(i); 34 for(int i=1;i<=n;i++) 35 sum[i]=sum[i-1]+(f[i]==i); 36 for(int i=1;i<=n;i++)if(num[i]) 37 { 38 if(num[i]==1&&sum[i]==all+1) 39 v[id[i]]=i,all++; 40 else if(num[i]+all==sum[i]) 41 all=sum[i]; 42 else num[i+1]+=num[i]; 43 } 44 for(int i=1;i<=n;i++) 45 printf("%d ",v[i]); 46 }