Pagini recente » Cod sursa (job #2170773) | Cod sursa (job #3232779) | Cod sursa (job #2867610) | Cod sursa (job #1094401) | Cod sursa (job #3272895)
#include <bits/stdc++.h>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int n, dp1[100004], dp2[100004];
vector<int> V[100004];
void dfs(int node, int father) {
dp1[node] = 0;
int maxi1 = 0, maxi2 = 0;
for (int num : V[node]) {
if (num != father) {
dfs(num, node);
if (dp1[num] > maxi1) {
maxi2 = maxi1;
maxi1 = dp1[num];
} else if (dp1[num] > maxi2) {
maxi2 = dp1[num];
}
}
}
dp1[node] = maxi1 + 1; // lungimea maximă până la o frunză
dp2[node] = maxi1 + maxi2 + 1; // diametrul trecând prin acest nod
}
int main() {
f >> n;
for (int i = 1; i < n; i++) {
int a, b;
f >> a >> b;
V[a].push_back(b);
V[b].push_back(a);
}
int ans = 0;
dfs(1, 0);
for (int i = 1; i <= n; i++) {
ans = max(ans, max(dp1[i], dp2[i]));
}
g << ans << '\n';
return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int t,n,i,j,a,b,dp1[200004],dp2[200004];
vector<int>V[200004];
void dfs(int node,int father){
int maxi1=0,maxi2=0,poz=0;
if (V[node].size()==1){
dp1[node]=1;
dp2[node]=0;
}
else {
for (int num=0;num<V[node].size();num++){
if (V[node][num]!=father){
dfs(V[node][num],node);
dp1[node]=max(dp1[node],dp1[V[node][num]]+1);
if (dp1[V[node][num]]>maxi1){
maxi1=dp1[V[node][num]];
poz=num;
}
}
}
V[node][poz]=0;
for (int num=0;num<V[node].size();num++){
if (V[node][num]!=father){
if (dp1[V[node][num]]>maxi2){
maxi2=dp1[V[node][num]];
}
}
}
V[node][poz]=maxi1;
dp2[node]=maxi1+maxi2+1;
}
}
int main()
{ f>>n;
for (i=1;i<n;i++){
f>>a>>b;
V[a].push_back(b);
V[b].push_back(a);
}
int ans=0;
dfs(1,0);
for (i=1;i<=n;i++){
//cout<<dp1[i]<<' ';
if (ans<dp2[i]){
ans=dp2[i];
}
if (ans<dp1[i]){
ans=dp1[i];
}
}
g<<ans<<'\n';
return 0;
}
*/