树形DP2F

T1 树的直径

我们使用\(f\)表示以\(u\)为根的子树，向下延伸的最远距离
那么\(f\)的初始值为0，表示\(u\)能向下延伸的最远距离是自己，\(f=0\)
\(ans=max(ans,f+f[v]+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[v]个\),那么直径的个数要加上\(num\)*\(num[v]\),刚开始\(num=1\)，表示距离为0的点有一个，就是自己,其余的部分，和更新最大值是相同的

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int maxn=100005;
4. int n,zj;
5. int f[maxn],num[maxn];
6. long long ans;
7. vector< pair<int,int> >g[maxn];
8. void dfs(int u,int fa){
9.         num[u]=1;
10.         for(auto x:g[u]){
11.                 int v=x.first;
12.                 int w=x.second;
13.                 if(v==fa) continue;
14.                 dfs(v,u);
15.                 int dis=f[v]+w;
16.                 if(dis+f[u]>zj){
17.                         zj=dis+f[u];
18.                         ans=num[u]*num[v];
19.                 }else if(dis+f[u]==zj){
20.                         ans+=num[u]*num[v];
21.                 }
22.                 if(dis>f[u]){
23.                         num[u]=num[v];
24.                         f[u]=dis;
25.                 }else if(dis==f[u])
26.                         num[u]+=num[v];
27.         }
28. }
29. int main(){
30.         cin>>n;
31.         for(int i=1;i<n;i++){
32.                 int x,y,z;
33.                 cin>>x>>y>>z;
34.                 g[x].push_back({y,z});
35.                 g[y].push_back({x,z});
36.         }
37.         dfs(1,-1);
38.         cout<<zj<<" "<

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！