Pagini recente » Monitorul de evaluare | Profil M@2Te4i | Monitorul de evaluare | Istoria paginii utilizator/mateivolo05 | Cod sursa (job #1958064)
#include <iostream>
#include <fstream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <stack>
#include <list>
#include <algorithm>
#include <limits.h>
using namespace std;
//longest chain in a tree
ifstream f("darb.in");
ofstream g("darb.out");
int LC[100001];
int LB[100001];
int m, n = 0; // m - nr of egdes
// n - nr of nodes, INDEXED from 1
vector<int> tree[100001];
int longestBranch(int root){
if(LB[root] != 0){
return LB[root];
}
LB[root] = 1;
vector<int> connectedNodes = tree[root];
if(connectedNodes.size() == 0){
return 1;
}
int maxx = INT_MIN;
for(int node: connectedNodes){
maxx = max(maxx, longestBranch(node));
}
LB[root] = maxx + 1;
return LB[root];
}
int longestChain(int root){
if(LC[root] != 0){
return LC[root];
}
LC[root] = 1;
vector<int> connectedNodes = tree[root];
if(connectedNodes.size() == 0){
return 1;
}
int maxLC = INT_MIN;
int maxLB = INT_MIN;
for(int node: connectedNodes){
maxLC = max(maxLC, longestChain(node));
}
if(connectedNodes.size() == 1){
maxLB = 1 + longestBranch(connectedNodes.back());
LC[root] = max(maxLC, 1 + maxLB);
} else {
int maxLB1 = INT_MIN, maxLB2 = INT_MIN;
for(int node: connectedNodes){
if (longestBranch(node) > maxLB1){
maxLB2 = maxLB1;
maxLB1 = longestBranch(node);
} else if(longestBranch(node) > maxLB2){
maxLB2 = longestBranch(node);
}
}
maxLB = maxLB1 + maxLB2;
}
LC[root] = max(maxLC, 1 + maxLB);
return LC[root];
}
int main(){
f >> n;
m = n - 1;
for(int i = 0; i < m; i++){
int from, to;
f >> from >> to;
tree[from].push_back(to);
}
/// print check
// for(int i = 1; i <= n; i++){
// vector<int> inter = tree[i];
// cout << i << ": ";
// for(int j = 0; j < inter.size(); j++){
// cout << inter[j] << " ";
// }
// cout << endl;
// }
//
g << longestChain(1) << endl;
return 0;
}