树形DP2F
T1 树的直径我们使用\(f\)表示以\(u\)为根的子树，向下延伸的最远距离
那么\(f\)的初始值为0，表示\(u\)能向下延伸的最远距离是自己，\(f=0\)
\(ans=max(ans,f+f+w)ans\)表示直径
错误1
如果有负边权，所以我把\(f\)的初值设置成为一个极小值，这样的话，和\(f\)的意义就背离了，所以不能这样设置，如果有负边权，我们就把\(ans\)的初值设置为极小值就可以了
如果我们把\(f\)设置成极小值，下述的图就会出错，找不到最长的直径为7
同时，直径指的是树上两点之间的最远距离，如果所有的边权都是负数，那么直径就是所有负边权的最大值
T2 直径的个数
我们先来看这棵树的直径长度是14，共有12个
考虑12个点对从何而来？4和8，9，10，5和8，9，10，依次类推
如果\((u,v)\)构成了直径，那么和\(f\)最远距离相同的点共有多少个，假设有\(num\)个，同理，也有\(num个\),那么直径的个数要加上\(num\)*\(num\),刚开始\(num=1\)，表示距离为0的点有一个，就是自己,其余的部分，和更新最大值是相同的
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,zj;
int f,num;
long long ans;
vector< pair<int,int> >g;
void dfs(int u,int fa){
num=1;
for(auto x:g){
int v=x.first;
int w=x.second;
if(v==fa) continue;
dfs(v,u);
int dis=f+w;
if(dis+f>zj){
zj=dis+f;
ans=num*num;
}else if(dis+f==zj){
ans+=num*num;
}
if(dis>f){
num=num;
f=dis;
}else if(dis==f)
num+=num;
}
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
g.push_back({y,z});
g.push_back({x,z});
}
dfs(1,-1);
cout<<zj<<" "<
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 谢谢楼主提供！
页:
[1]