HDU 2196 Computer（树形dp+换根法+树的直径）

向右看齐 2021-12-01 12:22 202阅读 0赞

## 题意：给出一棵树，求离每个节点最远的点的距离 ##

## 分析： ##

## 方法一：贪心做法，不会证明，找到直径的两个端点，分别dfs一下，求出两端到每个点分别的距离取最大值，树的直径作用很大啊。 ##

## 方法二：把无根树转化成有根树分析，对于每个节点，维护所有以当前节点为根的子树中距当前节点最远的距离和次远距离，二次扫描（两遍dfs）。 ##

## 参考：[https://blog.csdn.net/shuangde800/article/details/9732825][https_blog.csdn.net_shuangde800_article_details_9732825]、[http://www.mamicode.com/info-detail-1114779.html][http_www.mamicode.com_info-detail-1114779.html]。 ##

## 代码一（方法一）： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5+5;
    vector<int> G[N],L[N];
    int n,a,b,dis1[N],dis2[N],len,fa,fb;
    
    void dfs(int pre, int v, int d[], int x){
        d[v] = x;
        for (int i = 0; i < G[v].size(); ++i){
            int u = G[v][i];
            if (u == pre) continue;
            dfs(v, u, d, x + L[v][i]);
        }
        if (x > len){
            len = x;
            fa = v;
        }
    }
    
    int main(){
        while (~scanf("%d",&n)){
            for (int i = 0; i <= n; ++i){
                G[i].clear();
                L[i].clear();
            }
            for (int i = 2; i <= n; ++i){
                scanf("%d%d",&a,&b);
                G[a].push_back(i);
                G[i].push_back(a);
                L[a].push_back(b);
                L[i].push_back(b);
            }
            len = -1;
            dfs(-1, 1, dis1, 0);
            len = -1;
            dfs(-1, fa, dis1, 0);
            len = -1;
            dfs(-1, fa, dis2, 0);
            for (int i = 1; i <= n; ++i)
                printf("%d\n",max(dis1[i], dis2[i]));
        }
        return 0;
    }

## 代码二（方法二）： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=1e5+5;
    struct Edge{
        int ne,to,dis;
    }edge[N];
    
    int h[N],cnt=0;
    void add_edge(int f,int to,int c){
        edge[++cnt].ne=h[f];
        edge[cnt].to=to;
        edge[cnt].dis=c;
        h[f]=cnt;
    }
    
    int n,m;
    int f[N],g[N],t[N];
    /// f--最大值 g--次大值,都是向下走到的最远距离
    void dfs(int u,int fa){
        int v,x;
        int p=0,pp=0;///p--max pp--smaller than max
        for(int i=h[u];i;i=edge[i].ne){
            v=edge[i].to;
            if(v==fa)continue;
            dfs(v,u);
            x=f[v]+edge[i].dis;
            if(p<x) pp=p,p=x,t[u]=v;
            else if(pp<x) pp=x;///这一句话千万不要忘了加
        }
        f[u]=p,g[u]=pp;
        return ;
    }
    
    int q[N];   ///向上走到的最远距离
    void dfs2(int u,int fa){
        int v,x;
        for(int i=h[u];i;i=edge[i].ne){
            v=edge[i].to;
            if(v==fa)continue;
            if(v==t[u])x=g[u];
            else x=f[u];
            q[v]=max(q[u],x)+edge[i].dis;
            dfs2(v,u);
        }
        return ;
    }
    
    int main(){
    	int x,y,z;
        while(scanf("%d",&n)!=EOF){
            memset(h,0,sizeof(h));
            for(int i=2;i<=n;i++){
                scanf("%d%d",&x,&y);
                add_edge(i,x,y);
                add_edge(x,i,y);
            }
            f[1]=g[1]=0;
            dfs(1,0);
            q[1]=0;
            dfs2(1,0);
            for(int i=1;i<=n;i++)
                printf("%d\n",max(f[i],q[i]));
        }
        return 0;
    }

[https_blog.csdn.net_shuangde800_article_details_9732825]: https://blog.csdn.net/shuangde800/article/details/9732825
[http_www.mamicode.com_info-detail-1114779.html]: http://www.mamicode.com/info-detail-1114779.html