旅游规划
题意
思路
求树中每个节点是不是经过树中的最长路径
需要求出每个节点往下走的最长路径、往下走的次长路径、往上走的最长路径。这三个属性值可以确定：经过这个点的树中最长路径。
然后比较一下，树的直径。最后输出
代码
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
#define mst(s,_s) memset(s, _s, sizeof(s))
const double PI
= acos(-1.0);
const double eps
= 1e-6;
const int INF
= 0x3f3f3f3f;
const int N
= 1e6+100;
int T
,n
,m
;
int h
[N
],ne
[N
],e
[N
],idx
;
void add(int a
,int b
){
e
[idx
]=b
;
ne
[idx
]=h
[a
];
h
[a
]=idx
++;
}
int d1
[N
],d2
[N
];
int p1
[N
],up
[N
];
int is_leaf
[N
],dist
[N
];
int maxd
=0;
int dfs_d(int u
,int fa
)
{
d1
[u
]=d2
[u
]=-0x3f3f3f3f;
for(int i
=h
[u
];i
!=-1;i
=ne
[i
])
{
int j
=e
[i
];
if(j
==fa
) continue;
int d
=dfs_d(j
,u
)+1;
if(d
>d1
[u
])
{
p1
[u
]=j
;
d2
[u
]=d1
[u
];
d1
[u
]=d
;
}
else if(d
>d2
[u
])
{
d2
[u
]=d
;
}
}
if(d1
[u
]==-0x3f3f3f3f)
{
d1
[u
]=d2
[u
]=0;
is_leaf
[u
]=1;
}
maxd
=max(maxd
,d1
[u
]+d2
[u
]);
return d1
[u
];
}
void dfs_u(int u
,int fa
)
{
for(int i
=h
[u
];i
!=-1;i
=ne
[i
])
{
int j
=e
[i
];
if(j
==fa
) continue;
if(p1
[u
]==j
) up
[j
]=max(up
[u
],d2
[u
]) + 1;
else{
up
[j
]=max(up
[u
],d1
[u
])+1;
}
dfs_u(j
,u
);
}
}
int main() {
cin
>>n
;
memset(h
,-1,sizeof h
);
for(int i
=0;i
<n
;i
++)
{
int a
,b
;
cin
>>a
>>b
;
add(a
,b
);
add(b
,a
);
}
dfs_d(0,-1);
dfs_u(0,-1);
int res
=0;
for(int i
=0;i
<n
;i
++)
if(is_leaf
[i
])
d1
[i
]=d2
[i
]=0;
up
[0]=0;
for(int i
=0;i
<n
;i
++)
{
int _d3
[3]={d1
[i
],d2
[i
],up
[i
]};
sort(_d3
,_d3
+3);
res
=max(res
,_d3
[1]+_d3
[2]);
}
for(int i
=0;i
<n
;i
++)
{
int _d3
[3]={d1
[i
],d2
[i
],up
[i
]};
sort(_d3
,_d3
+3);
if(_d3
[1] + _d3
[2] ==maxd
)
cout
<<i
<<endl
;
}
return 0;
}
