2014
01-15

# Codeforces 34C Page Numbers-DFS[解题]

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are n cities in Berland. Each city has its index — an integer number from 1 to n.
The capital has index r1.
All the roads in Berland are two-way. The road system is such that there is exactly one path from the capital to each city, i.e. the road map looks like a tree. In Berland’s chronicles the road map is kept in the following way: for each city i,
different from the capital, there is kept number pi —
index of the last city on the way from the capital to i.

Once the king of Berland Berl XXXIV decided to move the capital from city r1 to
city r2. Naturally, after
this the old representation of the road map in Berland’s chronicles became incorrect. Please, help the king find out a new representation of the road map in the way described above.

Input

The first line contains three space-separated integers nr1r2 (2 ≤ n ≤ 5·104, 1 ≤ r1 ≠ r2 ≤ n)
— amount of cities in Berland, index of the old capital and index of the new one, correspondingly.

The following line contains n - 1 space-separated integers — the old representation of the road map. For each city, apart from r1,
there is given integer pi —
index of the last city on the way from the capital to city i. All the cities are described in order of increasing indexes.

Output

Output n - 1 numbers — new representation of the road map in the same format.

Sample test(s)
input
3 2 3
2 2

output
2 3
input
6 2 4
6 1 2 4 2

output
6 4 1 4 2

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 100005;

int n, r1, r2, sb;

vector<int> g[N];
int du[N], i;
int vis[N];
int ans[N];

void dfs(int now) {
vis[now] = 1;
for (int i = 0; i < g[now].size(); i++) {
int v = g[now][i];
if (vis[v]) continue;
ans[v] = now;
dfs(v);
}
}

int main() {
memset(vis, 0, sizeof(vis));
memset(du, 0, sizeof(du));
memset(g, 0, sizeof(g));
scanf("%d%d%d", &n, &r1, &r2);
for (i = 1; i <= n; i++) {
if (i == r1) continue;
scanf("%d", &sb);
g[i].push_back(sb);
g[sb].push_back(i);
du[i]++; du[sb]++;
}
dfs(r2);
int bo = 0;
for (i = 1; i <= n; i++) {
if (i == r2) continue;
if (bo++) printf(" ");
printf("%d", ans[i]);
}
printf("\n");
return 0;
}

1. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3