发布时间：2024-07-31

树形dp

树的最长路径

两次dfs做法(只适用于无负权边)

void solve(){
    int n;
    cin>>n;
    vector<int> adj[n+1],dis(n+1,-1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    queue<int> q;
    q.push(1);
    dis[1]=0;
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(auto v:adj[u]){
            if(dis[v]==-1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    int x=0,mx=-1;
    for(int i=1;i<=n;i++){
        if(dis[i]>mx){
            mx=dis[i];
            x=i;
        }
    }
    for(int i=1;i<=n;i++)dis[i]=-1;
    dis[x]=0;
    q.push(x);
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(auto v:adj[u]){
            if(dis[v]==-1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    mx=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,dis[i]);
    }
    cout<<mx;
}

树形dp(最大次大值更新)

枚举到当前节点时，直径一定是子分支的两个最大值连在一起作为直径

int dfs(int u,int fa){
    int d1=0,d2=0;
    for(auto v:adj[u]){
        if(v!=fa){
            int d=dfs(v,u)+w;
            if(d>=d1){
                d2=d1;
                d1=d;
            }
            else if(d>=d2)d2=d;
        }
    }
    ans=max(ans,d1+d2);
    return d1;
}

在树中找出两条不相交的路径，最大化二者长度的乘积
思路：

• 首先，按照最大次大值更新的方法可以更新出每棵子树的能找到的最长路径
• 然后就是要找除子树之外的另一条最长路径
  • 可以发现对于一个确定的u，每个v的子树外的点是不一样的，这就导致每次子树外的另一条路径不是定值
  • 思考从下往上找时的思路，是更新了当前节点的最长后，返回当前点的最长深度并对所有路径的最长值取max即g[u]=max(g[u],g[v])
  • 因此对于一个确定的v,应该将已经找到的最长路径长度mx和到每个根节点的长度up作为参数往下传
  • 那么对于up有可能是到根节点，也有可能是到令一个子节点的最底端
  • 因此可以先预处理，从每一个子节点的深度和u往上走的最长深度中找最大的三个值d1,d2,d3,和他们所属边的第一个节点son1,son2,son3
  • $ if (v=son_1):MX=max(mx,d_2+d_3),UP=d_2 $
  • $ if (v=son_2):MX=max(mx,d_1+d_3),UP=d_1 $
  • $ else: MX=max(d_1+d_2),UP=d_1 $

void solve(){
    int n;
    cin>>n;
    vector<int> adj[n+1],dep(n+1),g(n+1),f(n+1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    function<int(int,int)> dfs_u=[&](int u,int fa){
        int d1=0,d2=0;
        for(auto v:adj[u]){
            if(v==fa)continue;
            int d=dfs_u(v,u)+1;
            if(d>=d1)d2=d1,d1=d;
            else if(d>=d2)d2=d;
            dep[u]=max(dep[u],dep[v]+1);
            g[u]=max(g[u],g[v]);
        }
        g[u]=max(g[u],d1+d2);
        return d1;
    };
    ll ans=0;
    function<void(int,int,int,int)> dfs_d=[&](int u,int fa,int up,int mx){
        int d1=up,son1=fa,d2=0,son2=0,d3=0,son3=0;
        for(auto v:adj[u]){
            if(v==fa)continue;
            int d=dep[v]+1;
            if(d>=d1){
                d3=d2;
                son3=son2;
                d2=d1;
                son2=son1;
                d1=d;
                son1=v;
            }
            else if(d>=d2){
                d3=d2;
                son3=son2;
                d2=d;
                son2=v;
            }
            else if(d>=d3){
                d3=d;
                son3=v;
            }
        }
        for(auto v:adj[u]){
            if(v==fa)continue;
            ll MX,UP;
            if(son1==v){
                MX=max(mx,d2+d3);
                UP=d2;
            }
            else if(son2==v){
                MX=max(mx,d1+d3);
                UP=d1;
            }
            else{
                MX=max(mx,d1+d2);
                UP=d1;
            }
            ans=max(ans,MX*g[v]);
            dfs_d(v,u,UP+1,MX);
        }
    };
    dfs_u(1,0);
    dfs_d(1,0,0,0);
    cout<<ans<<"\n";
}