G换根dp的深入浅出

首先对于本题我来理解一下他需要求的是什么
需要对于每一个点求解出不包含当前点的最长路径由于对于每一个点都需要求解出来
所以一定是可继承性的所以我们可以考虑到换根dp
大方向可以明确是换根dp，我们考虑如何实现 alt u --> v
基于画图我们可以知道我们需要在换中传递的值有两个：
1.上面答案最大值
2.到达父节点的最长路径

传递到v的时候
1.就会变成到达u节点的最长路径中选两个的最大值和上面答案的最大值取max
2.等于到u父节点的最长路径+1

首先需要维护的本来的值就是儿子节点的答案我们可以通过一次dfs，求出每个节点的最大值和次大值来维护即可

void dfs1(int u,int fa){
    for(auto&v:g[u]){
        if(v==fa) continue;
        dfs1(v,u);
        dmx[u] = max(dmx[u],dmx[v]);// 表示当前u树中不包括u的最大路径是多少
        if(d1[v]+1>d1[u]){ // 最大值
            d2[u] = d1[u];
            d1[u] = d1[v] + 1;
        }
        else if(d1[v]+1>d2[u]){ // 次大致
            d2[u] = d1[v] +1;
        }
    }
    dmx[u] = max(dmx[u],d1[u]+d2[u]);
}

对于传递的内容维护最长

void dfs2(int u,int fa,int p1,int p2){
    multiset<int> s1,s2;
    s1.insert(0),s2.insert(0); // 为了防止越界
    s1.insert(p1),s2.insert(p2); // 传递下来的最大值
    
    for(auto&v:g[u]){ // 直接把所有儿子节点的贡献放进来
        if(v==fa) continue;
        s1.insert(dmx[v]);
        s2.insert(d1[v]+1);
    }
    ans[u] = *s1.rbegin();// 
    // 1.当前树中不包括u的最大路径
    // 2.p1表示当前点上面的最大值 
    // 两者取max即是当前点的最大值
    
    for(auto&v:g[u]){
        if(v==fa) continue;
        s1.erase(s1.find(dmx[v]));
        s2.erase(s2.find(d1[v]+1));// 考虑传递的时候不能有本来这个点的答案构成先删去
        int  np1 = max(*s1.rbegin(),*s2.rbegin()+*prev(prev(s2.end())));
        // 上面的点的最大答案，或者是到达u的路中选两个最大的求和
        int  np2 = *s2.rbegin()+1;// 经过u最长路径是到u的父节点中所有路径中的最大值+1
        dfs2(v,u,np1,np2);
        s1.insert(dmx[v]);
        s2.insert(d1[v]+1);
    }
}

最后完整代码

// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
const int N=100010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;
int d1[N],d2[N],dmx[N],ans[N];
vector<int> g[N];
void dfs1(int u,int fa){
    
    for(auto&v:g[u]){
        if(v==fa) continue;
        dfs1(v,u);
        dmx[u] = max(dmx[u],dmx[v]);
        if(d1[v]+1>d1[u]){
            d2[u] = d1[u];
            d1[u] = d1[v] + 1;
        }
        else if(d1[v]+1>d2[u]){
            d2[u] = d1[v] +1;
        }
    }
    dmx[u] = max(dmx[u],d1[u]+d2[u]);
}

void dfs2(int u,int fa,int p1,int p2){
    multiset<int> s1,s2;
    s1.insert(0),s2.insert(0);
    s1.insert(p1),s2.insert(p2);
    
    for(auto&v:g[u]){
        if(v==fa) continue;
        s1.insert(dmx[v]);
        s2.insert(d1[v]+1);
    }
    ans[u] = *s1.rbegin();
    
    for(auto&v:g[u]){
        if(v==fa) continue;
        s1.erase(s1.find(dmx[v]));
        s2.erase(s2.find(d1[v]+1));
        int  np1 = max(*s1.rbegin(),*s2.rbegin()+*prev(prev(s2.end())));
        int  np2 = *s2.rbegin()+1;
        dfs2(v,u,np1,np2);
        s1.insert(dmx[v]);
        s2.insert(d1[v]+1);
    }
}
void solve(){
    
    cin >> n;
    for(int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs1(1,1);
    dfs2(1,1,0,0);
    for(int i=1;i<=n;i++) cout << ans[i] << endl;
    return ;
}
signed main ()
{
    ios// 不能有printf puts scanf
    int t=1;
    while(t--){
    	 solve();
    }
}

题解 |G换根dp的深入浅出

G换根dp的深入浅出