Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <algorithm>
- struct Tree {
- Tree(int N) {
- edges.resize(N);
- depth.resize(N);
- visited.resize(N);
- answers.resize(N, -1);
- }
- void AddEdge(int u, int v);
- void DfsForDepth(int vertex, int dep);
- int FindMaxDepth();
- void FindDiameter();
- int DfsForDiameter(int vertex, int dep);
- void DfsForOthers(int vertex, int answer);
- void GetAnswer();
- std::vector<int> answers;
- private:
- std::vector<std::vector<int> > edges;
- std::vector<int> depth;
- std::vector<bool> visited;
- int DiameterBegin;
- int DiameterEnd;
- };
- void Tree::AddEdge(int u, int v) {
- edges[u].push_back(v);
- edges[v].push_back(u);
- }
- void Tree::DfsForDepth(int vertex, int dep) {
- visited[vertex] = true;
- depth[vertex] = dep;
- for (int i = 0; i < edges[vertex].size(); i++) {
- int u = edges[vertex][i];
- if (visited[u] == false) {
- DfsForDepth(u, dep + 1);
- }
- }
- }
- int Tree::FindMaxDepth() {
- int maxDepth = -1;
- int numMax;
- for (int i = 0; i < depth.size(); i++) {
- if (depth[i] > maxDepth) {
- maxDepth = depth[i];
- numMax = i;
- }
- }
- return numMax;
- }
- void Tree::FindDiameter() {
- visited.assign(visited.size(), false);
- DfsForDepth(0, 0);
- DiameterBegin = FindMaxDepth();
- visited.assign(visited.size(), false);
- DfsForDepth(DiameterBegin, 0);
- DiameterEnd = FindMaxDepth();
- }
- int Tree::DfsForDiameter(int vertex, int dep) {
- visited[vertex] = true;
- if (vertex == DiameterEnd) {
- answers[vertex] = dep;
- return 0;
- }
- int result = -1;
- for (int i = 0; i < edges[vertex].size(); i++) {
- int u = edges[vertex][i];
- if (!visited[u]) {
- result = DfsForDiameter(u, dep + 1);
- if (result != -1) {
- answers[vertex] = std::max(result + 1, dep);
- break;
- }
- }
- }
- return result + 1;
- }
- void Tree::DfsForOthers(int vertex, int answer) {
- visited[vertex] = true;
- if (answers[vertex] == -1) {
- answers[vertex] = answer;
- }
- for (int i = 0; i < edges[vertex].size(); i++) {
- int u = edges[vertex][i];
- if (!visited[u]) {
- DfsForOthers(u, answers[vertex] + 1);
- }
- }
- }
- void Tree::GetAnswer() {
- FindDiameter();
- visited.assign(visited.size(), false);
- DfsForDiameter(DiameterBegin, 0);
- visited.assign(visited.size(), false);
- DfsForOthers(DiameterBegin, -1);
- }
- int main() {
- int N;
- std::cin >> N;
- Tree tree(N);
- for (int i = 0; i < N - 1; i++) {
- int u, v;
- std::cin >> u >> v;
- tree.AddEdge(u, v);
- }
- tree.GetAnswer();
- for (int i = 0; i < tree.answers.size(); i++) {
- std::cout << tree.answers[i] << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement