jennie

树上dp求直径的模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int n;
vector<int> v[100001];
int x,y;
int f1[100001];
int f2[100001];
int ans;
void dfs(int x,int f){
    for(int i=0;i<v[x].size();++i){
        if(v[x][i]==f) continue;
        dfs(v[x][i],x);
        int tem=f1[v[x][i]]+1;
        if(tem>f1[x]){
            f2[x]=f1[x];
            f1[x]=tem;
        }else if(tem>f2[x]){
            f2[x]=tem;
        }
    }
    ans=max(ans,f2[x]+f1[x]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    cout<<ans;
    return 0;

}