记录编号	577679	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2012]Salaries	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	2.689 s
提交时间	2022-11-20 22:20:22	内存使用	49.95 MiB

// Problem: P3542 [POI2012]PEN-Salaries
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3542
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back

const int maxn = 1e6 + 5;
int n,rt,mx[maxn],pre[maxn],z[maxn],sum[maxn],cnt[maxn],pos[maxn];
std::vector<int> G[maxn];

void dfs(int u,int fa) {
	pos[mx[u] = z[u] ? z[u] : pre[mx[fa] - 1]] = u;
	++ sum[mx[u]];
	for(auto& v : G[u]) {
		if(v == fa)continue ;
		dfs(v , u);
	}
	return ;
}

int main() {
	freopen("salaries.in","r",stdin);
	freopen("salaries.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i)pre[i] = i;
	for(int i = 1;i <= n;++ i) {
		int p;
		scanf("%d %d",&p,&z[i]);
		if(p ^ i)G[p].pb(i);
		else rt = i;
		if(z[i])pre[z[i]] = z[i] - 1;
	}
	z[rt] = n;
	for(int i = 1;i <= n;++ i)
		pre[i] = pre[pre[i]];
	dfs(rt , 0);
	int cnt = 0;
	for(int i = 1;i <= n;++ i) {
		cnt += 1 - sum[i];
		if(!cnt&&sum[i] == 1)z[pos[i]] = i;
	}
	for(int i = 1;i <= n;++ i) {
		printf("%d\n",z[i]);
	}
	return 0;
}