Pagini recente » Cod sursa (job #2390884) | Cod sursa (job #678154) | Cod sursa (job #2350044) | Cod sursa (job #2026477) | Cod sursa (job #683018)
Cod sursa(job #683018)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#define MAXN 100001
using namespace std;
typedef unsigned int uint32;
typedef vector<vector<int> > Graph;
int K[MAXN];
int vRequests[MAXN];
int vLevels[MAXN];
Graph graph;
void DFS(const int node, const int level)
{
for (uint32 i=0; i<graph[node].size(); ++i)
{
vLevels[level+1] = graph[node][i];
if (K[graph[node][i]])
{
vRequests[graph[node][i]] = vRequests[vLevels[level+1-K[graph[node][i]]]]+1;
}
DFS(graph[node][i], level+1);
}
}
bool isRoot[MAXN] = {true};
int main()
{
int n;
fstream fin("cerere.in", fstream::in);
fstream fout("cerere.out", fstream::out);
fin >> n;
//cout << n << "\n";
graph.resize(n+1);
for (int i=1; i<=n; ++i)
{
fin >> K[i];
isRoot[i] = true;
}
for (int i=1; i<n; ++i)
{
int x,y;
fin >> x >> y;
graph[x].push_back(y);
isRoot[y] = false;
}
for (int i=1; i<=n; ++i)
{
if (isRoot[i])
{
vLevels[0] = i;
DFS(i, 0);
}
}
for (int i=1; i<=n; ++i)
{
fout << vRequests[i] << " ";
}
fout << "\n";
fin.close();
fout.close();
return 0;
}