Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- class Node
- {
- public:
- Node() : h(0) {}
- int h;
- vector<int> child;
- };
- int root;
- int max_path;
- vector<Node> nodes;
- bool mycmp(int a, int b)
- {
- return (nodes[b].h < nodes[a].h);
- }
- int DFS(int idx)
- {
- if (nodes[idx].child.empty()) {
- nodes[idx].h = 1;
- return 1;
- }
- for (int i=0;i<nodes[idx].child.size();i++) {
- nodes[idx].h = max(nodes[idx].h, DFS(nodes[idx].child[i]) + 1);
- }
- sort(nodes[idx].child.begin(), nodes[idx].child.end(), mycmp);
- if (nodes[idx].child.size() == 1) {
- max_path = max(max_path, nodes[nodes[idx].child[0]].h);
- }
- else {
- max_path = max(max_path, nodes[nodes[idx].child[0]].h + nodes[nodes[idx].child[1]].h);
- }
- return nodes[idx].h;
- }
- void calc(int idx)
- {
- for (int i=0;i<nodes[idx].child.size();i++) {
- nodes[idx].h = max(nodes[idx].h, DFS(nodes[idx].child[i]) + 1);
- }
- sort(nodes[idx].child.begin(), nodes[idx].child.end(), mycmp);
- if (nodes[idx].child.size() == 1) {
- max_path = max(max_path, nodes[nodes[idx].child[0]].h);
- }
- else {
- max_path = max(max_path, nodes[nodes[idx].child[0]].h + nodes[nodes[idx].child[1]].h);
- }
- }
- int main()
- {
- int n;
- int parent, child;
- while (cin >> n) {
- vector<int> pp(n, -1);
- root = -1;
- max_path = 0;
- nodes.clear();
- for (int i=0;i<n;i++) {
- Node node;
- nodes.push_back(node);
- }
- for (int i=0;i<n-1;i++) {
- cin >> parent >> child;
- pp[child] = parent;
- nodes[parent].child.push_back(child);
- }
- for (int i=0;i<n;i++) {
- if (pp[i] == -1) {
- root = i;
- break;
- }
- }
- calc(root);
- cout << max_path << endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment